Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR13-093 | 21st June 2013 01:00

A Generalization of Spira's Theorem and Circuits with Small Segregators or Separators


Authors: Anna Gal, Jing-Tang Jang
Publication: 21st June 2013 01:01
Downloads: 2917


Spira showed that any Boolean formula of size $s$ can be simulated in depth $O(\log s)$. We generalize Spira's theorem and show that any Boolean circuit of size $s$ with segregators of size $f(s)$ can be simulated in depth $O(f(s)\log s)$. If the segregator size is at least $s^{\varepsilon}$ for some constant $\varepsilon > 0$, then we can obtain a simulation of depth $O(f(s))$. This improves and generalizes a simulation of polynomial-size Boolean circuits of constant treewidth $k$ in depth $O( k^2 \log n)$ by Jansen and Sarma. Since the existence of small balanced separators in a directed acyclic graph implies that the graph also has small segregators, our results also apply to circuits with small separators. Our results imply that the class of languages computed by non-uniform families of polynomial-size circuits that have constant size segregators equals non-uniform $NC^1$.

Considering space bounded Turing machines to generate the circuits, for $f(s)\log^2 s$-space uniform families of Boolean circuits our small-depth simulations are also $f(s)\log^2 s$-space uniform. As a corollary, we show that the Boolean Circuit Value problem for circuits with constant size segregators (or separators) is in deterministic $SPACE (\log^2 n)$. Our results also imply that the Planar Circuit Value problem, which is known to be $P$-Complete, is in $SPACE (\sqrt{n} \log n)$. We also show that the Layered Circuit Value and Synchronous Circuit Value problems, which are both $P$-complete, are in $SPACE(\sqrt{n})$.

ISSN 1433-8092 | Imprint