Undergraduate Upends a 40-Year-Old Data Science Conjecture
This is a great story; bonus that it’s a notable improvement for the humble hash-table data structure:
Krapivin was not held back by the conventional wisdom for the simple reason that he was unaware of it. “I did this without knowing about Yao’s conjecture,” he said. His explorations with tiny pointers led to a new kind of hash table — one that did not rely on uniform probing. And for this new hash table, the time required for worst-case queries and insertions is proportional to (log x)^2 — far faster than x. This result directly contradicted Yao’s conjecture. Farach-Colton and Kuszmaul helped Krapivin show that (log x)^2 is the optimal, unbeatable bound for the popular class of hash tables Yao had written about.
Paper here — https://arxiv.org/abs/2501.02305 .
Tags: data-structures hash-tables cs programming coding papers optimization open-addressing