Conference Publications
Quadratic Probing Insertions Are ε^{−(1+o(1))} Time [arxiv]
with Yang Hu, William Kuszmaul, Stefan Walzer, Huacheng Yu, and Renfei Zhou
Preprint
Quadratic Probing Revisited: Smoothed Analysis and the Fall of Robin Hood [arxiv]
with Yang Hu, William Kuszmaul, Stefan Walzer, Huacheng Yu, and Renfei Zhou
Preprint
Stable Open Addressing and the Curse of Reappearance Dependencies
with Michael A. Bender, Bradley C. Kuszmaul, William Kuszmaul, Sike Lang, and Renfei Zhou
To appear in SODA 2027
Optimal Time-Space Tradeoff for Dynamic Difference-Encoded Dictionaries [arxiv]
with Guy E Blelloch, Yang Hu, William Kuszmaul, and Renfei Zhou
To appear in SODA 2027
Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck [arxiv]
with William Kuszmaul and Renfei Zhou
In SODA 2026
Fingerprint Filters are Optimal [arxiv]
with William Kuszmaul and Renfei Zhou
In FOCS 2025
Static Retrieval Revisited: To Optimality and Beyond [arxiv]
with Yang Hu, William Kuszmaul, Huacheng Yu, Junkai Zhang, and Renfei Zhou
In FOCS 2025
Optimal Static Fully Indexable Dictionaries [arxiv]
with Renfei Zhou
In ICALP 2025
Optimal Static Dictionary with Worst-Case Constant Query Time [arxiv]
with Yang Hu, Huacheng Yu, Junkai Zhang, and Renfei Zhou
In STOC 2025
Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification [arxiv]
with Josh Alman
In STOC 2025
Maximum Circuit Lower Bounds for Exponential-time Arthur Merlin [eccc]
with Lijie Chen, and Jiatu Li
In STOC 2025
Dynamic Dictionary with Subconstant Wasted Bits per Key [arxiv]
with Tianxiao Li, Huacheng Yu, and Renfei Zhou
In SODA 2024
Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries [arxiv]
with Tianxiao Li, Huacheng Yu, and Renfei Zhou
In FOCS 2023
Covered in Quanta Magazine
Dynamic “Succincter” [arxiv]
with Tianxiao Li, Huacheng Yu, and Renfei Zhou
In FOCS 2023
On the Perturbation Function of Ranking and Balance for Weighted Online Bipartite Matching [arxiv]
with Zhihao Gavin Tang, Yixuan Even Xu, Yuhao Zhang, and Renfei Zhou
In ESA 2023