
Simulating Time With Square-Root Space (And With Details)
Ryan Williams of the Institute for Advanced Study presents a detailed proof that every multitape Turing machine running in time t(n) can be simulated in space O(sqrt(t log t)), a landmark result in computational complexity. Delivered as part of the IAS Computer Science/Discrete Mathematics Seminar II, the talk works through the argument in a self-contained way, building up the necessary extension of the space-efficient Tree Evaluation algorithm recently discovered by Cook and Mertz at STOC 2024, which Williams identifies as the key insight enabling the simulation. The lecture runs over two hours and is aimed at an audience with background in theoretical computer science, walking through technical steps rather than summarizing them at a high level. It covers the history of time-space tradeoffs, the structure of the Tree Evaluation problem, and how the two results combine to improve the classical bound on simulating time-bounded computation with limited memory.