Date and time: Sep 12, 2025, 12-1:45pm
Location: Rice 109
Title: Simulating Time with Square-Root Space
Abstract:
How much time and space is needed to solve a specific problem? Time and space are the two most essential computational resources. Unsurprisingly in computational complexity, two critical questions are: what problems can be solved in a given amount of time, and what problems can be solved in a given amount of space. An immediate question is whether we can trade time for space, or vice versa. That is, suppose that a problem is solvable in time T, how much space S is needed to solve the same problem? Surprisingly, the progress on such time-space tradeoff is extremely slow—there has been no progress after Hopcroft, Paul, and Valiant proved that S = O(T / log T) since 1975. That was half a century ago!
Earlier this year, Prof. Ryan Williams (MIT) proved that S = O( √( T log T) ). It is a huge improvement in half a century, and it is indeed very surprising. The STOC 2025 Best Paper Award recognizes the paper by Williams. In this talk, I will illustrate the result at a high level. If time permits, I will also demonstrate the Tree Evaluation algorithm by Cook and Mertz (STOC 2024), an innovative and essential tool that saves space.
This talk is based on the following beautiful paper and video recordings of Williams:
Video at IAS: https://youtu.be/1qwDO5ulUFs
Video at TCS+: https://youtu.be/tM9ekW6FAS8