.jpg)
For Algorithms, a Little Memory Outweighs a Lot of Time
One computer scientist’s “stunning” proof is the first progress in 50 years on one of the most famous questions in computer science. The post For Algorithms, a Little Memory Outweighs a Lot of Time first appeared on Quanta Magazine
One July afternoon in 2024, Ryan Williams set out to prove himself wrong. Two months had passed since he’d hit upon a startling discovery about the relationship between time and memory in computing. It was a rough sketch of a mathematical proof that memory was more powerful than computer scientists believed: A small amount would be as helpful as a lot of time in all conceivable computations.
