Huacheng Yu - RankMe

103 papers A* 35A 6Misc 2Journal 56Unranked 3

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