For Algorithms, a Little Memory Outweighs a Lot of Time

For Algorithms, a Little Memory Outweighs a Lot of Time

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. Source