“You didn’t just come up with a cool hash table,” he remembers telling Krapivin. “You’ve actually completely wiped out a 40-year-old conjecture!”
A Rutgers undergraduate disproved Andrew Yao’s 1985 conjecture on hash table lookups. Worst-case queries scale with log squared, not linearly. Forty years of assumptions fell to one student’s hash table.