Huacheng Yu

Orcid: 0000-0003-1450-1896

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

Collaborative distances:

Dijkstra number² of three.
Erdős number³ of three.

Timeline

Legend:

Book

In proceedings

Article

PhD thesis

Dataset

Other

Links

On csauthors.net:

Bibliography

2025

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

[BibT_eX]

[DOI]

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

2024

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

[BibT_eX]

[DOI]

Proc. ACM Manag. Data, 2024

Optimal Static Dictionary with Worst-Case Constant Query Time.

[BibT_eX]

[DOI]

CoRR, 2024

Strong XOR Lemma for Information Complexity.

[BibT_eX]

[DOI]

Pachara Sawettamalya

Huacheng Yu

CoRR, 2024

A Strong Separation for Adversarially Robust ℓ<sub>0</sub> Estimation for Linear Sketches.

[BibT_eX]

[DOI]

CoRR, 2024

Dynamic Dictionary with Subconstant Wasted Bits per Key.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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

On the Amortized Complexity of Approximate Counting.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2024

2023

Sampling, Flowers and Communication.

[BibT_eX]

[DOI]

Huacheng Yu

Wei Zhan

Electron. Colloquium Comput. Complex., 2023

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

[BibT_eX]

[DOI]

Huacheng Yu

Wei Zhan

Electron. Colloquium Comput. Complex., 2023

Detecting TCP Packet Reordering in the Data Plane.

[BibT_eX]

[DOI]

Yufei Zheng

Huacheng Yu

Jennifer Rexford

CoRR, 2023

Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries.

[BibT_eX]

[DOI]

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

Dynamic "Succincter".

[BibT_eX]

[DOI]

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

Super-Logarithmic Lower Bounds for Dynamic Graph Problems.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Sepehr Assadi

Michael Kapralov

Huacheng Yu

Proceedings of the Approximation, 2023

2022

Nearly Optimal Static Las Vegas Succinct Dictionary.

[BibT_eX]

[DOI]

Huacheng Yu

SIAM J. Comput., June, 2022

Strong XOR Lemma for Communication with Bounded Rounds.

[BibT_eX]

[DOI]

Huacheng Yu

Electron. Colloquium Comput. Complex., 2022

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Optimal Bounds for Approximate Counting.

[BibT_eX]

[DOI]

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).

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Tight Distributed Sketching Lower Bound for Connectivity.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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

2020

Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds.

[BibT_eX]

[DOI]

Kasper Green Larsen

Omri Weinstein

Huacheng Yu

SIAM J. Comput., 2020

Fast Software Cache Design for Network Appliances.

[BibT_eX]

[DOI]

Proceedings of the 2020 USENIX Annual Technical Conference, 2020

Lower bound for succinct range minimum query.

[BibT_eX]

[DOI]

Mingmou Liu

Huacheng Yu

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

How to Store a Random Walk.

[BibT_eX]

[DOI]

Emanuele Viola

Omri Weinstein

Huacheng Yu

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

Faster Update Time for Turnstile Streaming Algorithms.

[BibT_eX]

[DOI]

Josh Alman

Huacheng Yu

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

Succinct Filters for Sets of Unknown Sizes.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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

2019

Pruning based Distance Sketches with Provable Guarantees on Random Graphs.

[BibT_eX]

[DOI]

Hongyang Zhang

Huacheng Yu

Ashish Goel

Proceedings of the World Wide Web Conference, 2019

Optimal succinct rank data structure via approximate nonnegative tensor decomposition.

[BibT_eX]

[DOI]

Huacheng Yu

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

2018

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture.

[BibT_eX]

[DOI]

Amir Abboud

Virginia Vassilevska Williams

Huacheng Yu

SIAM J. Comput., 2018

An improved combinatorial algorithm for Boolean matrix multiplication.

[BibT_eX]

[DOI]

Huacheng Yu

Inf. Comput., 2018

Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation.

[BibT_eX]

[DOI]

Jelani Nelson

Huacheng Yu

Electron. Colloquium Comput. Complex., 2018

2017

Techniques for proving data structure lower bounds.

[BibT_eX]

[DOI]

Huacheng Yu

PhD thesis, 2017

Cell-Probe Lower Bounds from Online Communication Complexity.

[BibT_eX]

[DOI]

Josh Alman

Joshua R. Wang

Huacheng Yu

Electron. Colloquium Comput. Complex., 2017

Distance Labelings on Random Power Law Graphs.

[BibT_eX]

[DOI]

Huacheng Yu

Hongyang Zhang

CoRR, 2017

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

[BibT_eX]

[DOI]

Jacob Teo Por Loong

Jelani Nelson

Huacheng Yu

CoRR, 2017

DecreaseKeys are expensive for external memory priority queues.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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

2016

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

[BibT_eX]

[DOI]

Omri Weinstein

Huacheng Yu

Electron. Colloquium Comput. Complex., 2016

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

[BibT_eX]

[DOI]

Huacheng Yu

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

2015

Finding Four-Node Subgraphs in Triangle Time.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Amir Abboud

Richard Ryan Williams

Huacheng Yu

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

2014

Finding orthogonal vectors in discrete structures.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Tengyu Ma

Xiaoming Sun

Huacheng Yu

Des. Codes Cryptogr., 2013

2011

A New Variation of Hat Guessing Games.

[BibT_eX]

[DOI]

Tengyu Ma

Xiaoming Sun

Huacheng Yu

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

Huacheng Yu

Timeline

Legend:

Links

On csauthors.net:

Bibliography

Loading...