Andrew Yao's 1985 conjecture about hash tables assumed that the best approach for probing was random selection, a view upheld for decades. However, researcher Krapivin, unaware of this conjecture, developed a new hash table method that significantly improved the efficiency of queries and insertions to (log x)². This result directly contradicts Yao’s assumption of worst-case time as simply x. Along with collaborators Farach-Colton and Kuszmaul, Krapivin's team established that (log x)² is the optimal bound for these hash tables, heralding a major advancement in the field, addressing a long-standing open problem in computer science.
Krapivin's new exploration led to a novel hash table that dispenses with uniform probing, achieving worst-case query times of (log x)^2, faster than Yao's conjectured x.
The findings not only provide a counterexample to Yao's long-accepted conjecture but offer the best-known answer for queries in this hash table class.
Guy Blelloch remarked on the beauty of the result, emphasizing its resolution of a classic hash table problem that had persisted for decades.
Sepehr Assadi expressed the significance of the work, noting that without this breakthrough, clarity on optimal query times could have eluded researchers for years.
Collection
[
|
...
]