Undergraduate upends a 40-year-old data science conjecture – Quanta Magazine

Martín Farach-Colton, a co-author of the “Tiny Pointers” paper and Krapivin’s former professor at Rutgers, was initially skeptical of Krapivin’s new design. Hash tables are among the most thoroughly studied data structures in all of computer science; the advance sounded too good to be true. But just to be sure, he asked a frequent collaborator (and a “Tiny Pointers” co-author), William Kuszmaul of Carnegie Mellon University, to check out his student’s invention. Kuszmaul had a different reaction. “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!” […]

“It’s not just that they disproved [Yao’s conjecture], they also found the best possible answer to his question,” said Sepehr Assadi(opens a new tab) of the University of Waterloo. “We could have gone another 40 years before we knew the right answer.”