BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Ryan Williams (Massachusetts Institute of Technology (MIT))
DTSTART:20251015T130000Z
DTEND:20251015T140000Z
DTSTAMP:20260423T035930Z
UID:FLAT/13
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/FLAT/13/">Si
 mulating time with square-root space</a>\nby Ryan Williams (Massachusetts 
 Institute of Technology (MIT)) as part of One FLAT World Seminar\n\n\nAbst
 ract\nWe show that for all functions $t(n) \\geq n$\, every multitape Turi
 ng machine running in time $t$ can be simulated using only $O(\\sqrt{t \\l
 og t})$ space. This is a substantial improvement over Hopcroft\, Paul\, an
 d Valiant's simulation of time $t$ in $O({t}/{\\log t})$ space from 50 yea
 rs ago [FOCS 1975\, JACM 1977]. Among other results\, our simulation impli
 es 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 explic
 it problems solvable in $O(n)$ space which require at least $n^2/poly(\\lo
 g n)$ time on every multitape Turing machine\, thereby making a little pro
 gress on the $\\text{P}$ versus $\\text{PSPACE}$ problem. Our simulation r
 educes the problem of simulating time-bounded multitape Turing machines to
  a series of implicitly-defined Tree Evaluation instances with nice parame
 ters\, leveraging the remarkable space-efficient algorithm for Tree Evalua
 tion recently found by Cook and Mertz [STOC 2024].\n
LOCATION:https://researchseminars.org/talk/FLAT/13/
END:VEVENT
END:VCALENDAR