Author

Huacheng Yu

View on Semantic Scholar

2 papers indexed here

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Aug 2026

Quadratic Probing Insertions Are $\epsilon^{-(1+o(1))}$

First proposed in 1968, quadratic probing has stood for more than half a century as one of the simplest and most widely used hash-table designs in computer science. It is conjectured that, at load factor $1 - \epsilon$, the hash table achieves $O(\epsilon^{-1})$ expected insertion time. But even proving a bound of the form $f(\epsilon^{-1})$ for any function $f$ has remained open. In this paper, we prove that the expected insertion time is $\epsilon^{-(1 + o(1))}$. This settles the complexity of the data structure up to sub-polynomial factors in $\epsilon^{-1}$.

Yang Hu, William Kuszmaul, Jingxun Liang et al. · 0 citations

Preprint Jul 2026

Adversarial Robustness for Small Frequency Moments and a Weak Equivalence Theorem for Turnstile Streams

It is proved that for any sub-multiplicative norm, the existence of an efficient classical linear sketch is equivalent to the existence of an efficient robust turnstile algorithm, up to polynomial factors, formalizing $L_1$ embeddability as the fundamental mechanism governing both models.

Elena Gribelyuk, Honghao Lin, David P. Woodruff et al. · 0 citations