Undergraduate Researcher Develops Faster Hash Table, Challenging a Long-Standing Conjecture

Andrew Krapivin, a former undergraduate at Rutgers University, has challenged a decades-old assumption in computer science. His research, originally inspired by a paper on ‘Tiny Pointers,’ led him to develop a new type of hash table that operates significantly faster than previously thought possible. His work contradicts a conjecture made by Turing Award-winning computer scientist Andrew Yao in 1985, which stated that the worst-case search time for hash tables could not be improved beyond a certain limit.

Krapivin, unaware of Yao’s conjecture at the time, devised a new method that reduces search and insertion times from a proportional x complexity to (log x)², significantly improving efficiency. Supported by computer scientists Martín Farach-Colton and William Kuszmaul, Krapivin’s findings were published in early 2025. Beyond disproving Yao’s conjecture, the study also demonstrated an even more surprising result: certain non-greedy hash tables can achieve constant-time searches, independent of how full they are.

This breakthrough deepens the understanding of data structures and could influence future computational applications. While immediate practical implementations are uncertain, experts believe the discovery may unlock new advancements in data storage and retrieval efficiency.