21 Yr Old Disproves 4 Decades Old Belief in Computing

Listen to 100s of Science Documentaries on Turing for Free. Check out the App at iOS: https://apps.apple.com/in/app/the-tur... Android: https://play.google.com/store/apps/de... or listen at https://theturingapp.com Link to Andrew's Paper on "Optimal Bounds for Open Addressing Without Reordering" https://arxiv.org/pdf/2501.02305 TIMESTAMPS: 00:00 - Introduction 02:09 - What is a Hash Function? 07:37 - Andrew's Education and Work 18:34 - How His Work Changes the Future Discover how Andrew Krapivin overturned a legendary 40-year-old conjecture in theoretical computer science regarding hash tables. In this video, we explore the mathematics of "Elastic Hashing" and how it shatters the speed limits once set by Turing Award winner Andrew Yao. For decades, the "speed limit" of data structures was thought to be set in stone. Hash tables are the "filing cabinets" of the internet, powering everything from database records to web browser passwords. However, computer scientists long believed that as these tables approached 99% capacity, performance would inevitably crash—a phenomenon known as the "problem of the full parking lot". In 1985, Andrew Yao codified this belief, suggesting that any "greedy" strategy for placing data was at the mercy of linear probability: if only 1 in 1,000 slots are empty, you’d have to check 1,000 slots to find one. This created a forced choice: you could have a fast hash table or a full one, but never both. Andrew Krapivin, a 21-year-old undergraduate at Rutgers, didn't even know this famous conjecture existed. While working on a side project for memory compression, he realized that traditional methods failed because they were "greedy"—they always grabbed the first available spot, which created massive "traffic jams" of data. Krapivin’s solution, Elastic Hashing, is brilliantly counterintuitive. Instead of taking the first open slot, the algorithm intentionally skips empty spaces to create "firebreaks". These strategic gaps prevent data clusters from merging, keeping the system running with the snap and speed of a nearly empty structure—even at 99.99% capacity. This discovery isn't just a mathematical curiosity; it has massive implications for the future of Edge AI and database efficiency. Explore science like never before - accessible, thrilling, and packed with awe-inspiring moments. Fuel your curiosity with 100s of free, curated STEM audio shows. Credits: Simons Institute for the Theory of Computing UC Berkeley EECS Rutgers University