Any computation can be rerun in the square root of its memory

Every computation spends two things: time, the number of steps it takes, and memory, the scratch space it needs to hold its work. We tend to feel these are bound together, that a job which runs for a long time must also pile up a large amount of working memory along the way. For fifty years the math seemed to agree. The best anyone could prove was that a long computation could be redone using almost that much memory again, shaved down by only a whisker.

In 2025 Ryan Williams proved something far stranger, and it was the first real movement on this question in half a century. Take any computation that runs for a given stretch of time. He showed it can always be redone using only about the square root of the memory it appeared to need. A run of a million steps, which looked like it might demand a million cells of scratch space, can be replayed in roughly a thousand. A trillion steps fold down to about a million. The longer the computation, the more absurd the saving becomes.

This is the part I keep turning over. It does not mean your laptop needs less memory tomorrow. It is a proof that the saving is always possible, not a program you can download, and the trick has a price in time: you throw away partial results and work them out again when you need them, trading memory you do not have for time you do. But the fact that it can be done at all rewrites something we thought we understood. Memory turns out to be far cheaper than time. Almost anything you can compute, you can compute in a thimble of space, as long as you are willing to redo the work.

It is also a hairline crack in one of the oldest walls in the field, the question of whether time and memory are truly separate resources. The crack does not bring the wall down. But for fifty years it had not moved at all, and now it has, by a square root. What gets me is how long the obvious-seeming thing stood unquestioned. Everyone felt that remembering and redoing were a fair trade. It took half a century, and one proof, to learn how lopsided that trade really is.