Computer Science/Discrete Mathematics Seminar II

We will go in-depth into the proof that for all functions $t(n) \geq n$, every multitape Turing machine running in time $t$ can be simulated in space only $O(\sqrt{t \log t})$. We will attempt to be completely self-contained. To that end, we will describe a necessary extension of the remarkable space-efficient algorithm for Tree Evaluation recently found by Cook and Mertz [STOC 2024], which is the real surprise that makes the simulation possible.