Huacheng Yu

According to our database, Huacheng Yu authored at least 53 papers between 2011 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

Static Retrieval Revisited: To Optimality and Beyond.

Yang Hu, William Kuszmaul, Jingxun Liang, Huacheng Yu, Junkai Zhang, Renfei Zhou

CoRR, October, 2025

A (Very) Nearly Optimal Sketch for <i>k</i>-Edge Connectivity Certificates.

Pachara Sawettamalya, Huacheng Yu

CoRR, October, 2025

Optimal streaming algorithm for detecting ℓ₂ heavy hitters in random order streams.

Santhoshini Velusamy, Huacheng Yu

CoRR, September, 2025

Strong XOR Lemma for Information Complexity.

Pachara Sawettamalya, Huacheng Yu

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Optimal Static Dictionary with Worst-Case Constant Query Time.

Yang Hu, Jingxun Liang, Huacheng Yu, Junkai Zhang, Renfei Zhou

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness.

Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Near-Optimal Relative Error Streaming Quantile Estimation via Elastic Compactors.

Elena Gribelyuk, Pachara Sawettamalya, Hongxun Wu, Huacheng Yu

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

2024

Simple & Optimal Quantile Sketch: Combining Greenwald-Khanna with Khanna-Greenwald.

Elena Gribelyuk, Pachara Sawettamalya, Hongxun Wu, Huacheng Yu

Proc. ACM Manag. Data, 2024

A Strong Separation for Adversarially Robust ℓ₀ Estimation for Linear Sketches.

Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou

CoRR, 2024

Dynamic Dictionary with Subconstant Wasted Bits per Key.

Tianxiao Li, Jingxun Liang, Huacheng Yu, Renfei Zhou

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Sampling, Flowers and Communication.

Huacheng Yu, Wei Zhan

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output Functions.

Huacheng Yu, Wei Zhan

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

A Strong Separation for Adversarially Robust ℓ0 Estimation for Linear Sketches.

Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

On the Amortized Complexity of Approximate Counting.

Ishaq Aden-Ali, Yanjun Han, Jelani Nelson, Huacheng Yu

Proceedings of the Approximation, 2024

2023

Detecting TCP Packet Reordering in the Data Plane.

Yufei Zheng, Huacheng Yu, Jennifer Rexford

CoRR, 2023

Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut.

Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly.

Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Huacheng Yu

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries.

Tianxiao Li, Jingxun Liang, Huacheng Yu, Renfei Zhou

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Dynamic "Succincter".

Tianxiao Li, Jingxun Liang, Huacheng Yu, Renfei Zhou

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Super-Logarithmic Lower Bounds for Dynamic Graph Problems.

Kasper Green Larsen, Huacheng Yu

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

On Constructing Spanners from Random Gaussian Projections.

Sepehr Assadi, Michael Kapralov, Huacheng Yu

Proceedings of the Approximation, 2023

2022

Strong XOR Lemma for Communication with Bounded Rounds.

Huacheng Yu

Electron. Colloquium Comput. Complex., 2022

Optimal Bounds for Approximate Counting.

Jelani Nelson, Huacheng Yu

Proceedings of the PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

Strong XOR Lemma for Communication with Bounded Rounds : (extended abstract).

Huacheng Yu

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Almost optimal super-constant-pass streaming lower bounds for reachability.

Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Tight Distributed Sketching Lower Bound for Connectivity.

Huacheng Yu

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs.

Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

Fast Software Cache Design for Network Appliances.

Dong Zhou, Huacheng Yu, Michael Kaminsky, David G. Andersen

Proceedings of the 2020 USENIX Annual Technical Conference, 2020

Nearly optimal static Las Vegas succinct dictionary.

Huacheng Yu

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Lower bound for succinct range minimum query.

Mingmou Liu, Huacheng Yu

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

How to Store a Random Walk.

Emanuele Viola, Omri Weinstein, Huacheng Yu

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Faster Update Time for Turnstile Streaming Algorithms.

Josh Alman, Huacheng Yu

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Succinct Filters for Sets of Unknown Sizes.

Mingmou Liu, Yitong Yin, Huacheng Yu

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems.

Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena, Huacheng Yu

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Pruning based Distance Sketches with Provable Guarantees on Random Graphs.

Hongyang Zhang, Huacheng Yu, Ashish Goel

Proceedings of the World Wide Web Conference, 2019

Optimal succinct rank data structure via approximate nonnegative tensor decomposition.

Huacheng Yu

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation.

Jelani Nelson, Huacheng Yu

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018

Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds.

Kasper Green Larsen, Omri Weinstein, Huacheng Yu

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Cell-probe lower bounds from online communication complexity.

Josh Alman, Joshua R. Wang, Huacheng Yu

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

2017

Techniques for proving data structure lower bounds.

Huacheng Yu

PhD thesis, 2017

Distance Labelings on Random Power Law Graphs.

Huacheng Yu, Hongyang Zhang

CoRR, 2017

Fillable arrays with constant time operations and a single bit of redundancy.

Jacob Teo Por Loong, Jelani Nelson, Huacheng Yu

CoRR, 2017

DecreaseKeys are expensive for external memory priority queues.

Kasper Eenberg, Kasper Green Larsen, Huacheng Yu

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Beating Brute Force for Systems of Polynomial Equations over Finite Fields.

Daniel Lokshtanov, Ramamohan Paturi, Suguru Tamaki, R. Ryan Williams, Huacheng Yu

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

2016

Cell-probe lower bounds for dynamic problems via a new communication model.

Huacheng Yu

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication.

Omri Weinstein, Huacheng Yu

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture.

Amir Abboud, Virginia Vassilevska Williams, Huacheng Yu

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Finding Four-Node Subgraphs in Triangle Time.

Virginia Vassilevska Williams, Joshua R. Wang, Richard Ryan Williams, Huacheng Yu

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

More Applications of the Polynomial Method to Algorithm Design.

Amir Abboud, Richard Ryan Williams, Huacheng Yu

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

An Improved Combinatorial Algorithm for Boolean Matrix Multiplication.

Huacheng Yu

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Finding orthogonal vectors in discrete structures.

Ryan Williams, Huacheng Yu

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2013

On a conjecture of Butler and Graham.

Tengyu Ma, Xiaoming Sun, Huacheng Yu

Des. Codes Cryptogr., 2013

2011

A New Variation of Hat Guessing Games.

Tengyu Ma, Xiaoming Sun, Huacheng Yu

Proceedings of the Computing and Combinatorics - 17th Annual International Conference, 2011