Huacheng Yu

Publication Activity (10 Years)

Years Active: 2011-2024
Publications (10 Years): 72

Top Topics

External Memory

Johnson Lindenstrauss

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Huacheng Yu, Wei Zhan
Sampling, Flowers and Communication. ITCS (2024)
Elena Gribelyuk, Pachara Sawettamalya, Hongxun Wu, Huacheng Yu
Simple & Optimal Quantile Sketch: Combining Greenwald-Khanna with Khanna-Greenwald. Proc. ACM Manag. Data 2 (2) (2024)
Huacheng Yu, Wei Zhan
Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output Functions. ITCS (2024)
Tianxiao Li, Jingxun Liang, Huacheng Yu, Renfei Zhou
Dynamic Dictionary with Subconstant Wasted Bits per Key. SODA (2024)
Huacheng Yu, Wei Zhan
Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output Functions. CoRR (2023)
Kasper Green Larsen, Huacheng Yu
Super-Logarithmic Lower Bounds for Dynamic Graph Problems. FOCS (2023)
Huacheng Yu, Wei Zhan
Sampling, Flowers and Communication. Electron. Colloquium Comput. Complex. (2023)
Kasper Green Larsen, Huacheng Yu
Super-Logarithmic Lower Bounds for Dynamic Graph Problems. CoRR (2023)
Tianxiao Li, Jingxun Liang, Huacheng Yu, Renfei Zhou
Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries. CoRR (2023)
Huacheng Yu, Wei Zhan
Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output Functions. Electron. Colloquium Comput. Complex. (2023)
Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Huacheng Yu
Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly. ITCS (2023)
Tianxiao Li, Jingxun Liang, Huacheng Yu, Renfei Zhou
Dynamic Dictionary with Subconstant Wasted Bits per Key. CoRR (2023)
Tianxiao Li, Jingxun Liang, Huacheng Yu, Renfei Zhou
Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries. FOCS (2023)
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu
Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut. SODA (2023)
Tianxiao Li, Jingxun Liang, Huacheng Yu, Renfei Zhou
Dynamic "Succincter". CoRR (2023)
Yufei Zheng, Huacheng Yu, Jennifer Rexford
Detecting TCP Packet Reordering in the Data Plane. CoRR (2023)
Tianxiao Li, Jingxun Liang, Huacheng Yu, Renfei Zhou
Dynamic "Succincter". FOCS (2023)
Sepehr Assadi, Michael Kapralov, Huacheng Yu
On Constructing Spanners from Random Gaussian Projections. APPROX/RANDOM (2023)
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut. Electron. Colloquium Comput. Complex. (2022)
Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Huacheng Yu
Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly. Electron. Colloquium Comput. Complex. (2022)
Jelani Nelson, Huacheng Yu
Optimal Bounds for Approximate Counting. PODS (2022)
Huacheng Yu
Nearly Optimal Static Las Vegas Succinct Dictionary. SIAM J. Comput. 51 (3) (2022)
Sepehr Assadi, Michael Kapralov, Huacheng Yu
On Constructing Spanners from Random Gaussian Projections. CoRR (2022)
Huacheng Yu
Strong XOR Lemma for Communication with Bounded Rounds. CoRR (2022)
Ishaq Aden-Ali, Yanjun Han, Jelani Nelson, Huacheng Yu
On the amortized complexity of approximate counting. CoRR (2022)
Huacheng Yu
Strong XOR Lemma for Communication with Bounded Rounds : (extended abstract). FOCS (2022)
Huacheng Yu
Strong XOR Lemma for Communication with Bounded Rounds. Electron. Colloquium Comput. Complex. (2022)
Huacheng Yu
Tight Distributed Sketching Lower Bound for Connectivity. SODA (2021)
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu
Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs. ICALP (2021)
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability. Electron. Colloquium Comput. Complex. 28 (2021)
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs. CoRR (2021)
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu
Almost optimal super-constant-pass streaming lower bounds for reachability. STOC (2021)
Dong Zhou, Huacheng Yu, Michael Kaminsky, David G. Andersen
Fast Software Cache Design for Network Appliances. USENIX Annual Technical Conference (2020)
Mingmou Liu, Yitong Yin, Huacheng Yu
Succinct Filters for Sets of Unknown Sizes. ICALP (2020)
Mingmou Liu, Huacheng Yu
Lower bound for succinct range minimum query. STOC (2020)
Huacheng Yu
Tight Distributed Sketching Lower Bound for Connectivity. CoRR (2020)
Huacheng Yu
Nearly optimal static Las Vegas succinct dictionary. STOC (2020)
Emanuele Viola, Omri Weinstein, Huacheng Yu
How to Store a Random Walk. SODA (2020)
Kasper Green Larsen, Omri Weinstein, Huacheng Yu
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. SIAM J. Comput. 49 (5) (2020)
Mingmou Liu, Yitong Yin, Huacheng Yu
Succinct Filters for Sets of Unknown Sizes. CoRR (2020)
Josh Alman, Huacheng Yu
Faster Update Time for Turnstile Streaming Algorithms. SODA (2020)
Mingmou Liu, Huacheng Yu
Lower Bound for Succinct Range Minimum Query. CoRR (2020)
Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena, Huacheng Yu
Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems. CoRR (2020)
Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena, Huacheng Yu
Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems. FOCS (2020)
Jelani Nelson, Huacheng Yu
Optimal bounds for approximate counting. CoRR (2020)
Hongyang Zhang, Huacheng Yu, Ashish Goel
Pruning based Distance Sketches with Provable Guarantees on Random Graphs. WWW (2019)
Jelani Nelson, Huacheng Yu
Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation. SODA (2019)
Josh Alman, Huacheng Yu
Faster Update Time for Turnstile Streaming Algorithms. CoRR (2019)
Huacheng Yu
Optimal succinct rank data structure via approximate nonnegative tensor decomposition. STOC (2019)
Emanuele Viola, Omri Weinstein, Huacheng Yu
How to Store a Random Walk. CoRR (2019)
Huacheng Yu
Nearly Optimal Static Las Vegas Succinct Dictionary. CoRR (2019)
Kasper Green Larsen, Omri Weinstein, Huacheng Yu
Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds. STOC (2018)
Huacheng Yu
Optimal Succinct Rank Data Structure via Approximate Nonnegative Tensor Decomposition. CoRR (2018)
Kasper Green Larsen, Omri Weinstein, Huacheng Yu
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. ITA (2018)
Huacheng Yu
An improved combinatorial algorithm for Boolean matrix multiplication. Inf. Comput. 261 (2018)
Jelani Nelson, Huacheng Yu
Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation. CoRR (2018)
Jelani Nelson, Huacheng Yu
Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation. Electron. Colloquium Comput. Complex. 25 (2018)
Josh Alman, Joshua R. Wang, Huacheng Yu
Cell-probe lower bounds from online communication complexity. STOC (2018)
Amir Abboud, Virginia Vassilevska Williams, Huacheng Yu
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture. SIAM J. Comput. 47 (3) (2018)
Daniel Lokshtanov, Ramamohan Paturi, Suguru Tamaki, R. Ryan Williams, Huacheng Yu
Beating Brute Force for Systems of Polynomial Equations over Finite Fields. SODA (2017)
Huacheng Yu, Hongyang Zhang
Distance Labelings on Random Power Law Graphs. CoRR (2017)
Kasper Green Larsen, Omri Weinstein, Huacheng Yu
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. Electron. Colloquium Comput. Complex. 24 (2017)
Josh Alman, Joshua R. Wang, Huacheng Yu
Cell-Probe Lower Bounds from Online Communication Complexity. Electron. Colloquium Comput. Complex. 24 (2017)
Jacob Teo Por Loong, Jelani Nelson, Huacheng Yu
Fillable arrays with constant time operations and a single bit of redundancy. CoRR (2017)
Josh Alman, Joshua R. Wang, Huacheng Yu
Cell-Probe Lower Bounds from Online Communication Complexity. CoRR (2017)
Kasper Eenberg, Kasper Green Larsen, Huacheng Yu
DecreaseKeys are expensive for external memory priority queues. STOC (2017)
Kasper Green Larsen, Omri Weinstein, Huacheng Yu
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. CoRR (2017)
Omri Weinstein, Huacheng Yu
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication. FOCS (2016)
Omri Weinstein, Huacheng Yu
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication. Electron. Colloquium Comput. Complex. 23 (2016)
Kasper Eenberg, Kasper Green Larsen, Huacheng Yu
DecreaseKeys are Expensive for External Memory Priority Queues. CoRR (2016)
Huacheng Yu
Cell-probe lower bounds for dynamic problems via a new communication model. STOC (2016)
Omri Weinstein, Huacheng Yu
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication. CoRR (2016)
Amir Abboud, Virginia Vassilevska Williams, Huacheng Yu
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture. STOC (2015)
Virginia Vassilevska Williams, Joshua R. Wang, Richard Ryan Williams, Huacheng Yu
Finding Four-Node Subgraphs in Triangle Time. SODA (2015)
Huacheng Yu
Cell-probe Lower Bounds for Dynamic Problems via a New Communication Model. CoRR (2015)
Huacheng Yu
An Improved Combinatorial Algorithm for Boolean Matrix Multiplication. CoRR (2015)
Huacheng Yu
An Improved Combinatorial Algorithm for Boolean Matrix Multiplication. ICALP (1) (2015)
Amir Abboud, Richard Ryan Williams, Huacheng Yu
More Applications of the Polynomial Method to Algorithm Design. SODA (2015)
Ryan Williams, Huacheng Yu
Finding orthogonal vectors in discrete structures. SODA (2014)
Tengyu Ma, Xiaoming Sun, Huacheng Yu
On a conjecture of Butler and Graham. Des. Codes Cryptogr. 69 (3) (2013)
Tengyu Ma, Xiaoming Sun, Huacheng Yu
A New Variation of Hat Guessing Games CoRR (2011)
Tengyu Ma, Xiaoming Sun, Huacheng Yu
A New Variation of Hat Guessing Games. COCOON (2011)
Tengyu Ma, Xiaoming Sun, Huacheng Yu
On a Conjecture of Butler and Graham CoRR (2011)