Improved Bounds on the Space Complexity of Circuit Evaluation

by Yakov Shalunov

Oded's comments

A few months ago, Ryan Williams presented a significant improvement in the space complexity of emulating time-bounded computation by using the breakthrough algorithm of James Cook and Ian Mertz for Tree Evaluation. Applying this space-efficient emulation of time to the known algorithm for Circuit Evaluation, Ryan also obtain a space-efficient emulation of circuit size.

The main conceptual observation of the current paper is that reducing circuit size to computation time and emulating time via solving the Tree Evaluation problem is the wrong path. One can and should directly reduce Circuit Evaluation to Tree Evaluation, without passing through the Turing Machine model.

Consider a topological sort of the gates of the given $s$-sized circuit and partition the vertices into $h=s/b$ blocks of size $b$. If the gates of each block were fed only by other gates of this block and at most a constant number of gates from other blocks, then we could easily reduced the circuit evaluation to tree evaluation for $O(1)$-ary trees of height $h$ such that each gate in the tree operates on $b$-bit long strings. Note that what matters here is the depth of the resulting DAG (representing the feeding relation between blocks) and the in-degree of vertices in the DAG but not the number of vertices in the DAG, which is going to be replaced by an $O(1)$-ary tree of height $h$.

To get rid of the foregoing assumption, we just use auxiliary vertices. Specifically, the foregoing DAG (of blocks) has $h$ vertices and there are edges going between blocks. Now we can replace all edges going from vertex $i$ to vertex $j$ by a directed path of length $j-i$ that carries the relevant information. Envision this path as going from level $i$ to level $j$, with intermediate (auxiliary) vertices at levels $i+1,...,j-1$. Now, we merge all auxiliary vertices that are going to the same destination as easrly as possible. E.g., suppose that there are paths from levels $i_1,...,i_t$ going to level $j$, then we have a first merge at level $i_2+1$, where the path that goes through levels $i_1,i_1+1,....,i_2,i_2+1$ merges with the new path that starts at level $i_2$. Note that these merges involved onlty two vertices at a time, and so eventualy level $j$ is feed by a single auxilary vertex.

Note that each of the auxiliary vertices carries at most $2b$ bits (which correspond to the wires that fee into the gates of the corresponding block from all prior blocks). Hence, we obtaine an instance of the Tree Evaluation problem of heigh $h$ in which each vertex carries at most $2b$ bits (rather thanh $b$).

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

See ECCC TR25-078.


Back to list of Oded's choices.