For Algorithms, a Little Memory Outweighs a Lot of Time
Theoretical computer scientist Ryan Williams returns to the Institute this fall as the architect of a proof described as “stunning” and “massive.” Ben Brudaker of Quanta Magazine interviewed Williams about his revolutionary result and its significance for our understanding of the relationship between computational time and space.
For decades, computer scientists in the field of complexity theory—the branch that Williams has always been drawn to, which deals with questions of resources like time and space in computing—have been working within the confines of a basic premise. Algorithms require time to run, and space (or memory) to store data while they do so. Because computational space can be reused, it was suspected to be a much more powerful resource than time, which is non-recyclable.
Though the concept seems intuitive, establishing a rigorous proof of it has stumped researchers. Williams hadn’t set out to solve this problem until a group of his students at MIT gave a presentation on a seemingly unrelated landmark algorithm devised by Ian Mertz, Visitor (2022) in the School of Mathematics, and James Cook. (A few months earlier, Mertz gave a talk on this very model at the Institute). Williams saw a connection to the space versus time question; applying it allowed him to develop the universal simulation previously thought impossible. Though he searched for flaws in the argument for months, he couldn’t find any.
Williams’s finding stunned the mathematical community. A past Member (2008–09) in the School of Mathematics, Williams will return to IAS in September as a von Neumann Fellow in the Computer Science and Discrete Mathematics program led by Betsey Overdeck Theory of Computing Professor Irit Dveer Dinur and Herbert H. Maass Professor Avi Wigderson. According to Quanta, upon finding out about Williams’s proof, Wigderson sent Williams an email with a concise subject line: “You blew my mind.”
“I still have a hard time believing it,” Williams told Quanta. “It just seems too good to be true.”
Read the full article at Quanta Magazine.
