Undergraduate Upends a 40-Year-Old Data Science Conjecture
https://www.quantamagazine.org/undergraduate-upends-a-40-year-old-data-science-conjecture-20250210/
--
Ah, this really hits close to home. Back in a distant past, I was working on a problem that challenged the accepted wisdom of the time. When I proposed it to my ‘advisor’, it was dismissed outright because it “violated” what we thought we knew about vanishing gradients. Years later, a paper proved not only that it was possible but that it was actually quite effective.
I’ve seen the same pattern throughout my career in various companies; deeply ingrained assumptions that only get questioned during those rare, paradigm-shifting moments, like our own little 1492s. It’s fascinating how often we realize, in hindsight, how wrong we were.
That’s why this hash table breakthrough genuinely makes me happy. Here’s an undergraduate who simply… went ahead and disproved Yao’s 40-year-old conjecture about uniform hashing being optimal; probably because they didn’t know they “weren’t supposed to” question it. They just saw a problem, approached it with fresh eyes, and ended up improving probe complexity beyond what the field thought was possible.
It’s kind of vindicating, you know? It’s a powerful reminder of why we need to **always keep questioning our assumptions in computer science**; especially the ones that feel too fundamental to challenge. Sure, theoretical frameworks are essential for progress, but real breakthroughs often come from someone who hasn’t yet learned what’s considered “impossible.”
And the fact that this happened with hash tables; literally one of the first data structures we teach. This makes it even better.
It really makes me wonder what other “solved” problems in CS are just waiting for someone to revisit with a fresh perspective.
But it’s also a warning; as we lean more on machine learning and automated reasoning, are we limiting discovery by sticking too closely to established theories? Finding the balance between leveraging proven frameworks and staying open to challenging core assumptions is crucial for real progress.
Link to the paper https://arxiv.org/pdf/2501.02305