Date: Thursday, October 9, 2025
Time: 11:45 a.m. to 12:45 p.m.
Location: G01 Gates Hall
Speaker: Ryan Williams, Professor of Electrical Engineering and Computer Science at MIT
Abstract: How much time does it take to solve a problem? How much memory or space do we need? Applying work done in the 1970s at Cornell, along with new insights from the past two years, I will describe a new mathematical relationship between these two questions. In short, one only requires a surprisingly low amount of memory to simulate a huge variety of efficient computations.
Our findings allow us to understand other fundamental questions. Given that a problem can be solved by an algorithm using low memory, is there another algorithm which can solve the problem quickly? The mathematical formalization of this question is known as P versus PSPACE, which is a necessary stepping stone towards P versus NP. We will show how our work provides a little progress towards resolving P versus PSPACE.
Bio: Ryan Williams received an A.B. and M.Eng. from Cornell and completed a PhD at Carnegie Mellon under Manuel Blum. Following postdocs at the Institute for Advanced Study and IBM Almaden, he was Assistant Professor of Computer Science at Stanford from 2011-2016, and is presently Professor of Electrical Engineering and Computer Science at MIT and a von Neumann Fellow at the Institute for Advanced Study in Princeton, NJ. His awards include a Sloan Fellowship, an NSF CAREER fellowship, a Microsoft Research Faculty Fellowship, a Faculty Research Innovation Fellowship, and a Goedel Prize (2024).
Website: https://people.csail.mit.edu/rrw/
