Improved Bounds on the Space Complexity of Circuit Evaluation

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)$.

14 pages