Undergraduate Upends a 40-Year-Old Data Science Conjecture | Quanta Magazine

An undergraduate student at Rutgers University developed a revolutionary new hash table design that disproved a 40-year-old computer science conjecture by Andrew Yao, demonstrating faster data retrieval times than previously thought possible. The breakthrough shows that hash tables can achieve query times proportional to (log x)² instead of x, and in non-greedy cases, can maintain constant average query times regardless of table fullness.