Quadratic probing, introduced in 1968, remains one of the simplest and most widely adopted hash‑table schemes. For decades researchers have conjectured that at load factor $1-\epsilon$ the expected insertion time should be $O(\epsilon^{-1})$, yet no bound of the form $f(\epsilon^{-1})$ had been proved.
The paper delivers a breakthrough: the expected insertion time of quadratic probing is $\epsilon^{-(1+o(1))}$. In other words, the bound matches the conjectured $\epsilon^{-1}$ up to a sub‑polynomial factor. The authors achieve this by a fine‑grained probabilistic analysis of the probe sequence and novel techniques for handling the regime where $\epsilon\to0$.
This result settles a half‑century‑old open problem and provides a solid theoretical foundation for further practical optimizations of hash tables.
Blogger's Review: The authors finally close the long‑standing gap between conjecture and proof for quadratic probing. While constant‑factor tuning remains an engineering matter, having a tight asymptotic guarantee is a major step forward for both theory and practice.