Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-078 | 20th June 2025 02:13

Improved Bounds on the Space Complexity of Circuit Evaluation

RSS-Feed

Abstract:

Williams (STOC 2025) recently proved that time-$t$ multitape Turing machines can be simulated using $O(\sqrt{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(\sqrt{s} \cdot \mathrm{polylog}\; s)$ space algorithm for evaluating size $s$ circuits.
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(\sqrt{s \log s})$ space and providing a proof with fewer abstraction layers.
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(\sqrt{t} \log t)$.



ISSN 1433-8092 | Imprint