2026-08-21T16:32:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27384 2026-08-21T14:42:37Z ddc:004 open_access

Some Recent Developments in Space Complexity (Invited Talk) Williams, R. Ryan time lower bound space complexity multitape Turing machine P versus PSPACE tree evaluation problem Given a function, what is the minimal memory necessary to compute it? We will describe some old [John E. Hopcroft et al., 1977; Wolfgang J. Paul and Rüdiger Reischuk, 1981; Joseph Y. Halpern et al., 1986] and new algorithmic developments that give surprisingly low-space solutions to this question in many cases. We will survey the recent proof [Ryan Williams, 2026] that TIME[t] is contained in SPACE[√{t log t}] for the multitape Turing machine model, and the engine that makes the proof possible: the amazing Cook-Mertz algorithm [James Cook and Ian Mertz, 2024] for a problem called Tree Evaluation [Stephen A. Cook et al., 2012]. We will also briefly outline some new developments and generalizations that we've recently proved, pushing the low-space frontier beyond multitape Turing machines. The latter is joint work with Danil Sibgatullin (to appear). Schloss Dagstuhl – Leibniz-Zentrum für Informatik R. Ryan Williams 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.3 urn:nbn:de:0030-drops-273845 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.3 eng https://creativecommons.org/licenses/by/4.0/legalcode