Teenager Disproves a 4-Decade-Old Belief in Computing

ELI5 / TLDR

Computers store data in a kind of digital filing cabinet built for speed. For forty years, everyone believed the same thing: as the cabinet fills up, finding a free drawer has to get slower and slower — there was no way around it. A 21-year-old undergraduate, who didn’t even know this belief existed, stumbled onto a side project and accidentally proved everyone wrong. His trick was almost embarrassingly simple: sometimes, leave a perfectly good empty drawer empty on purpose. That one counterintuitive idea broke a wall that two generations of computer scientists thought was permanent.

The Full Story

The digital filing cabinet

Start with a problem every computer faces constantly: how do you find one specific thing among millions, instantly?

Imagine a library with no order at all. You want The Great Gatsby, so you walk the shelves checking every book until you find it. With a million books, that’s a long afternoon. Computer scientists call this “linear time” — the more books, the longer the hunt. Far too slow for a machine that needs answers in microseconds.

The clever fix is a structure called a hash table. Think of it as a filing system with a magic formula. You feed the formula the name of what you’re storing — say, the title The Great Gatsby — and it spits out a number, like 42. That number is the address. You put the book on Shelf 42. Later, when you want it back, you run the title through the same formula, get 42 again, and walk straight to it. No searching. The book is just there.

This is everywhere. Every time a database pulls a customer record, a browser checks a saved password, or a router forwards a packet, a hash table is almost certainly doing the work. It’s the internet’s filing cabinet.

The trouble with a full cabinet

The magic has a catch. The formula is a blunt instrument — it maps a huge number of possible names onto a limited number of shelves. So eventually two different things get sent to the same shelf. Two books, one slot. That’s called a collision, and the system has to do something about it.

The elegant approach — the one this story is about — is called open addressing. The rule is simple: one item per slot, no exceptions. If Shelf 42 is taken and a new book wants it, the system tries Shelf 43, then 44, then 45, walking forward until it finds an empty one. Each peek at a slot is called a probe.

Now picture this as a parking lot. When the lot is 10% full, you pull in and park immediately. But when it’s 99% full — 990 of 1,000 spaces taken — you circle for ten minutes hunting that one open spot. The fuller the lot, the longer the hunt. That’s the whole problem in one image.

The forty-year speed limit

In 1985, a giant of the field named Andrew Yao — a Turing Award winner, the field’s equivalent of a Nobel laureate — measured exactly how bad this gets.

He used a single number to describe how packed the table is. Call it x: it’s the inverse of the free space. If the table is 99% full, 1% is free, so x is 100. If it’s 99.9% full, x is 1,000. Bigger x means a tighter squeeze.

Yao studied what are called greedy algorithms — the obvious, sensible kind. A greedy algorithm grabs the first empty slot it finds, no hesitation, no looking ahead. Why wouldn’t it? An empty spot is an empty spot. His verdict was grim: with a greedy strategy, the work to insert a new item grows linearly with x. Double how packed the table is, double the work. Pack it ten times tighter, the system crawls ten times slower.

Then he went further with a conjecture — an educated claim he couldn’t fully prove — about the best anyone could ever do. His proposal: the smartest possible strategy is to just scatter data purely at random. Randomness, he said, was the ceiling. You could not beat chaos.

This hardened into law. For forty years the lesson was: you get a fast table or a full table, never both. Want speed? Leave a chunk of your memory deliberately empty. Wasted space was simply the toll you paid.

The accidental challenger

Enter Andrew Krapivin, an undergraduate at Rutgers double-majoring in math and computer science, who read research papers for fun. In late 2021 he found one called “Tiny Pointers.”

A quick translation. A pointer, in a computer, is just an address — a number saying “the data lives over here.” In enormous systems with billions of items, those addresses become big numbers, and big numbers eat memory. The Tiny Pointers paper showed a way to shrink them.

Krapivin wanted to shrink them even further. But tiny pointers have a requirement: to use a small address, your data has to be packed tightly — no sprawling across a half-empty landscape. Which meant he needed a hash table that could run nearly full and still stay fast. The exact thing Yao had declared impossible. Except Krapivin had never heard of Yao’s result. He just tried the standard methods, watched them choke as the table filled, and decided to build his own.

The counterintuitive move

Here is where he questioned the one assumption nobody questioned: should the algorithm always be greedy?

He noticed that grabbing the first open slot has a hidden cost. When everyone always takes the first opening, items pile up into clusters — long unbroken runs of filled slots. And clusters are self-reinforcing. The longer a run gets, the more likely a new item lands inside it and has to walk all the way to its far end, extending it further.

These runs are the traffic jams of the hash table.

At 99% full, a single jam can stretch thousands of slots. Krapivin’s question: what if the algorithm showed a little restraint? He built a strategy he called Elastic Hashing, and its central idea sounds almost wrong. When inserting an item, the algorithm probes a sequence of spots — and might find an empty one early. But instead of taking it, it sometimes skips it on purpose, leaving it empty.

Why throw away a perfectly good spot? Because that deliberate gap acts as a firebreak — like the cleared strips that stop a wildfire from spreading. Strategic empty slots keep clusters from merging into one giant jam. You sacrifice a tiny convenience now to keep the whole structure healthy.

Mountain into molehill

Krapivin ran the simulations expecting a modest improvement. What he got broke the rules.

The link between fullness and speed was no longer linear. It no longer tracked x at all. It now followed a much gentler logarithmic curve — the insert time grew with the square of the logarithm of x, written log(x)².

The difference is staggering at scale. Take a wildly packed table where x is one million. Under Yao’s linear law, the worst case is a million probes — unusable. Under Krapivin’s: the logarithm of a million is about 20, squared is 400. One million versus four hundred. A table could now be filled to 99.999% and still move with the speed of an empty one.

He brought it to his professor, Martín Farach-Colton, who was — reasonably — skeptical. A conjecture by a Turing laureate had stood for forty years against the sharpest minds alive. If the answer were “just skip a spot sometimes,” surely someone would have noticed. But he knew Krapivin was unusual, and pulled in a third person: William Kuszmaul of Carnegie Mellon, a specialist in exactly these structures. Kuszmaul checked the probability math, and it landed:

“You didn’t just come up with a cool hash table. You’ve actually completely wiped out a 40-year-old conjecture!”

The second, bigger surprise

The three spent a year turning the idea into bulletproof proof, published as “Optimal Bounds for Open Addressing Without Reordering.” Then they found something even stranger.

Yao’s 1985 work had set a second limit — not just on the worst case, but on the average time to find data, which he said must also grow as the table fills. But that proof, too, assumed greedy algorithms. Krapivin’s wasn’t greedy. So the team discovered a variant where the average search time doesn’t grow at all — it stays constant.

Read that again: a memory bank effectively 100% full, where finding any item is, on average, as fast as if it were empty. The mechanism is the same firebreak idea taken to its limit — the empty slots get spaced so perfectly evenly that you’re never more than a short hop from one.

Finally, they proved they’d hit bottom. They derived a lower bound showing log(x)² is the absolute floor for this class of table. No future algorithm, known or unknown, can beat it. Krapivin hadn’t just found a better answer — he’d found the best possible one.

The paper landed in January 2025, was called “beautiful” by CMU’s Guy Blelloch, and was named one of Quanta Magazine’s biggest computer science breakthroughs of 2025. One reviewer noted the field got lucky — it might have spent another forty years believing in a wall that wasn’t there.

Key Takeaways

Hash tables find data by feeding its name into a formula that returns its storage address — turning a slow shelf-by-shelf search into instant lookup.
Collisions (two items sent to the same slot) are inevitable; open addressing resolves them by walking forward to the next free slot, counting each peek as a “probe.”
The old belief (Yao, 1985): as a table fills, probe time must grow linearly with how packed it is (x), and pure randomness is the best you can do. Result: fast or full, pick one.
Yao’s proof only covered greedy algorithms — ones that always grab the first open slot.
Greedy grabbing creates self-reinforcing clusters — long runs of filled slots that act like gravity wells and become traffic jams.
Krapivin’s Elastic Hashing: sometimes skip an open slot on purpose. The deliberate gaps act as firebreaks that stop clusters from merging.
The payoff: worst-case insert time drops from linear in x to log(x)² — a million-probe nightmare becomes ~400.
A variant makes average search time constant even at ~100% full — finding data is as fast in a packed table as an empty one.
They also proved log(x)² is the optimal floor — no algorithm can ever beat it.
Practical upside: edge devices (phones, watches, sensors) can run memory at ~99% capacity instead of leaving 20–30% empty, enabling leaner systems, faster databases, better caches.

Claude’s Take

This is a real result, not a hype piece dressed up as one. The paper (“Optimal Bounds for Open Addressing Without Reordering”) was accepted to FOCS — one of the two top venues in theoretical computer science — and the Quanta coverage and named endorsements (Blelloch, Assadi) are genuine. The video gets the core ideas right and, refreshingly, doesn’t fudge the math: log(x)² vs linear-in-x is the actual headline, and the constant-time average-case variant is the actual second act.

A few honest caveats the breezy “teenager destroys legend” framing glosses over. First, this lives in theory-land. The bounds are asymptotic — they describe behavior as numbers get enormous. Whether your laptop’s hash table gets faster tomorrow depends on constant factors and cache behavior that asymptotic math ignores; real-world wins here are plausible but not automatic. Second, “disproves a belief” is slightly dramatic. Yao’s theorems were never wrong — they were correct about greedy algorithms. What fell was his conjecture about the limit across all strategies, and it fell precisely because Krapivin stepped outside the greedy assumption Yao’s analysis lived inside. The lesson is less “genius topples titan” and more “the unexamined assumption was load-bearing” — which is the more interesting story anyway.

The “didn’t even know the conjecture existed” angle is real and worth sitting with: not knowing the wall was there is arguably why he walked through it. That’s a genuine pattern in research, not just a nice anecdote. Docking a point because the channel leans on the prodigy narrative harder than the ideas need — the ideas can carry themselves. An 8: substantial, accurate, and well-fermented, just wrapped in a slightly louder bow than the content warrants.