2026-07-23T20:56:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27045 2026-07-23T11:36:18Z ddc:004 open_access

Improved Bounds on the Space Complexity of Circuit Evaluation Shalunov, Yakov circuit value problem CVP space complexity tree evaluation problem Williams (STOC 2025) recently proved that time-t multitape Turing machines can be simulated using O(√{t log t}) space using the Cook-Mertz (STOC 2024) tree evaluation procedure. As Williams notes, applying this result to fast algorithms for the circuit value problem implies an O(√s ⋅ polylog s) space algorithm for evaluating circuits with s gates. In this work, we provide a direct reduction from circuit value to tree evaluation without passing through Turing machines, simultaneously improving the bound to O(√{s log s}) space and providing a proof with fewer layers of abstraction. This result can be thought of as a "sibling" result to Williams' for circuit complexity instead of time; in particular, using the fact that time-t Turing machines have size O(t log t) circuits, we can recover a slightly weakened version of Williams' result, simulating time-t machines in space O(√t log t). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yakov Shalunov 2026 Is Part Of LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2026.3 urn:nbn:de:0030-drops-270451 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.3 eng https://creativecommons.org/licenses/by/4.0/legalcode