In a groundbreaking 1985 publication, computer scientist Andrew Yao, who later received the prestigious A.M. Turing Award, posited that among hash tables with specific characteristics, the most effective method for locating a single element or finding an empty slot is through random exploration—an approach referred to as uniform probing. He further claimed that in the worst-case scenario, particularly when searching for the last vacant position, one could never perform better than x. For four decades, the consensus among computer scientists has been that Yao’s hypothesis held true.
Krapivin, however, was undeterred by established beliefs, primarily because he was unaware of them. “I approached this without any knowledge of Yao’s conjecture,” he explained. His experiments using miniature pointers led to the development of a new type of hash table—one that does not depend on uniform probing. For this innovative hash table, the time taken for the worst-case queries and insertions is proportional to (log x)2, which is significantly quicker than x. This finding directly refuted Yao’s conjecture. With the assistance of Farach-Colton and Kuszmaul, Krapivin established that (log x)2 represents the optimal, unsurpassable threshold for the widely recognized class of hash tables discussed by Yao.
“This discovery is remarkable as it tackles and resolves such a foundational issue,” remarked Guy Blelloch from Carnegie Mellon.
“It’s not merely that they disproved [Yao’s conjecture], but they’ve also pinpointed the best possible answer to his question,” noted Sepehr Assadi of the University of Waterloo. “We could have spent another 40 years without knowing the right answer.”
