A Rutgers University undergraduate’s discovery has shaken the computer science community by disproving a widely-held conjecture on hash tables. Andrew Krapivin, who was working on a paper called “Tiny Pointers” when he stumbled upon a potential way to miniaturize pointers in memory.
Krapivin realized that traditional hash table approaches needed improvement and turned to data structures known as hash tables. He teamed up with his former professor, MartÃn Farach-Colton, and Carnegie Mellon University colleague, William Kuszmaul, to explore new designs. Their collaboration led to the development of a revolutionary new kind of hash table that outperforms traditional methods.
The breakthrough came when they demonstrated that this new design can find elements faster than previously thought possible, directly contradicting a 40-year-old conjecture by Andrew Yao. The results show that the time required for worst-case queries and insertions is proportional to (log x)2, significantly faster than x.
Furthermore, Krapivin, Farach-Colton, and Kuszmaul also found an average query time that’s better than previously thought possible, even for non-greedy hash tables. Their discovery has significant implications for understanding data structures and could lead to future breakthroughs in computing.
Source: https://www.quantamagazine.org/undergraduate-upends-a-40-year-old-data-science-conjecture-20250210