Undergraduate Upends a 40-Year-Old Data Science Conjecture : programming – Andrew Krapivin et all invente a faster hashing algorithm
Posted by jpluimers on 2025/06/26
From a while back: [Wayback/Archive] Undergraduate Upends a 40-Year-Old Data Science Conjecture : programming which has a “TL;DR for non CS people” and a “Here’s an explanation” well worth reading.
It’s about the work of Andrew Krapivin with co-authors Martín Farach-Colton and William Kuszmaul.
A young computer scientist and two colleagues show that searches within data structures called hash tables can be much faster than previously deemed possible.
Reminder to self to find any real world implementations of this new hashing algorithm.
Materials are the “easier” article [Wayback/Archive] Undergraduate Upends a 40-Year-Old Data Science Conjecture | Quanta Magazine which refers to the actual paper:
- [Wayback/Archive] [2501.02305] Optimal Bounds for Open Addressing Without Reordering
In this paper, we revisit one of the simplest problems in data structures: the task of inserting elements into an open-addressed hash table so that elements can later be retrieved with as few probes as possible. We show that, even without reordering elements over time, it is possible to construct a hash table that achieves far better expected search complexities (both amortized and worst-case) than were previously thought possible. Along the way, we disprove the central conjecture left by Yao in his seminal paper “Uniform Hashing is Optimal”. All of our results come with matching lower bounds.
- [Wayback/Archive] PDF: Optimal Bounds for Open Addressing Without Reordering Mart ́ın Farach-Colton, Andrew Krapivin, William Kuszmaul [Wayback PDF View/PDF View]
- [Wayback/Archive] Optimal Bounds for Open Addressing Without Reordering – experimental HTML rendering; requires JavaScript for proper viewing.
The discovery feels kind of similar to the George Dantzig story two open problems in statistical theory which he had mistaken as homework.
Note that, for me, the “easiest” explanation still is in the Reddit post I referenced at the top.
Via:
- [Wayback/Archive] Wladimir Mufty: “Sometimes a fresh perspective …” – SURF Mastodon Pilot
Sometimes a fresh perspective leads to revolutionary insights 💚. Without intending to Andrew Krapivin, as an undergraduate student 👨🎓, turned around the 40 years old paradidigm on #hashtable lookups 🗄️!
After the #DeepSeek results, another great example that #innovation does not always come from business cases or throwing billions 💰 and energy resources into the game. Sometimes it simply comes from curiosity and a different way of looking at a challenge!
- [Wayback/Archive] ShīnChvën – Revolutionizing Hash Tables: An Undergraduate’s Breakthrough
Query: [Wayback/Archive] Andrew Krapivin faster hash table implementation – Google Search
--jeroen
The Wiert Corner - irregular stream of stuff 
Leave a comment