LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Simulating Time With Square-Root Space (And With Details)
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Simulating Time With Square-Root Space (And With Details)

136 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

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.

At a glance

Lecture facts

Runtime compared with the other 734 Mathematics lectures
Runtime2 h 16 m
Compared with MathematicsLonger than 100%
Source channelInstitute for Advanced Study (YouTube)