TCS+ talk *this week*: Wednesday, April 23, Ryan Williams, MIT
Clement Canonne
This is a reminder that the next TCS+ talk is taking place this week, Wednesday, April 23rd at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). The speakers' slides will be made available at https://sites.google.com/view/tcsplus/welcome/past-talks after the talk.
If you’d like to join the Zoom talk, please sign up using the form at https://sites.google.com/view/tcsplus/welcome/next-tcs-talk. The talk will also be recorded and posted shortly afterwards on our YouTube channel, here: http://www.youtube.com/user/TCSplusSeminars.
Hoping to see you all there,
The organizers
-------------------------------
Speaker: Ryan Williams (MIT)
Title: Simulating Time With Square-Root Space
Abstract: We show 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})$. This is a substantial improvement over Hopcroft, Paul, and Valiant’s simulation of time $t$ in $O(t/\log t)$ space from 50 years ago [FOCS 1975, JACM 1977]. Among other results, our simulation implies that bounded fan-in circuits of size $s$ can be evaluated on any input in only $\sqrt{s} \cdot poly(\log s)$ space, and that there are explicit problems solvable in $O(n)$ space which require at least $n^{2-\varepsilon}$ time on a multitape Turing machine for all $\varepsilon > 0$, thereby making a little progress on the $P$ versus $PSPACE$ problem.
Our simulation reduces the problem of simulating time-bounded multitape Turing machines to a series of implicitly-defined Tree Evaluation instances with nice parameters, leveraging the remarkable space-efficient algorithm for Tree Evaluation recently found by Cook and Mertz [STOC 2024].