Undergraduate Disproves 40-Year-Old Conjecture, Invents New Kind of Hash Table

hash-tablesdata-structuresalgorithm-theorycomputer-scienceandrew-yao

Abstraction: New hash table design breaks 40-year-old worst-case query time bound

Key points:

Andrew Krapivin, then an undergraduate at Rutgers University, invented a new hash table design while working on "tiny pointers" that achieves worst-case query/insertion time proportional to (log x)^2, vs. the previously assumed optimal of x (where x measures how close the table is to 100% full).
This directly disproved Andrew Yao's 1985 conjecture (Yao won the Turing Award) that x was the unbeatable lower bound for uniform-probing hash tables.
Even more surprising: the new design achieves a constant average query time regardless of how full the hash table is — a result the authors themselves did not expect.
Krapivin was unaware of Yao's conjecture when he made the discovery ("I did this without knowing about Yao's conjecture"), illustrating how ignorance of conventional wisdom can enable breakthroughs.
Co-authors Martin Farach-Colton (NYU) and William Kuszmaul (CMU) verified and extended the result; published January 2025 on arXiv.
Hash tables date to the early 1950s and are among the most studied data structures in computer science; immediate applications unclear but the theoretical result resolves long-open questions.

Connections: Carnegie Mellon University · Rutgers University · Hash Tables · Data Structures · Algorithm Theory