FOR ALGORITHMS, A LITTLE MEMORY OUTWEIGHS A LOT OF TIME

Summary from the TLDR newsletter

Ryan Williams, a theoretical computer scientist at the Massachusetts Institute of Technology, recently posted a proof online on the relationship between time and memory in computing. The proof, which showed that memory was more powerful than computer scientists had previously believed, established a mathematical procedure for transforming any algorithm, no matter what it does, into a form that uses much less space. It also implies there are calculations that can't be computed in certain amounts of time, offering a new way to attack one of the oldest open problems in computer science.