<p>We know that languages defined by (poly-sized) Boolean formulae <em>equals</em> <a href="https://en.wikipedia.org/wiki/NC_(complexity)" rel="noreferrer"><span class="math-container">$\mathbf{NC}^1$</span></a>: that Boolean formulae can be simulated in <span class="math-container">$\mathbf{NC}^1$</span> was shown by Brent/Spira [B,S], and  the converse is quite trivial (simply duplicate the circuit whenever there is a ''collision''). A proof can be found, e.g., in <a href="https://www.cs.toronto.edu/%7Etoni/Courses/Complexity2015/lectures/lecture7.pdf" rel="noreferrer">this</a> lecture note by Pitassi (Theorem 3).</p>
<p>Boolean formulae (since the underlying graph is a binary tree) can be thought of as circuits with <a href="https://en.wikipedia.org/wiki/Treewidth" rel="noreferrer">treewidth</a> <span class="math-container">$1$</span>, where treewidth of a circuit can be defined as the treewidth of the graph obtained by ignoring the direction of the wires. Gal and Jang [GJ] extended the result in [B,S] by showing that a circuit of size <span class="math-container">$s$</span> with treewidth <span class="math-container">$w$</span> can be simulated in depth <span class="math-container">$w\log(s)$</span>. <em>My question is whether the converse is also true</em>: e.g., whether <span class="math-container">$\mathbf{NC}^2$</span> can be simulated using  circuits with treewidth <span class="math-container">$\log(s)$</span> with only a polynomial blow-up (and more generally, whether <span class="math-container">$\mathbf{NC}^i$</span> can be simulated using circuits with treewidth <span class="math-container">$O(\log^{i-1}(s))$</span>).</p>
<p>Intuitively, this should hold (by following the tree decomposition and then using the duplicating trick). But I could not find any resource regarding this (which makes me wonder whether it is false and there is a blow-up in some step). Any pointers would be appreciated!</p>
<p>[B]: Brent, <em>The Parallel Evaluation of General Arithmetic Expressions</em>. Journal of the ACM, 1974.</p>
<p>[GJ]: Gàl and Jang, <em>A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators</em>,  Inf. Comput., 2016.</p>
<p>[S]: Spira, <em>On time-hardware complexity tradeoffs for Boolean functions</em>. Hawaii Symp. on System Sciences, 1971.</p>

CC BY-SA 4.0
2021-02-28T12:23:08.950Z
Did you mean to ask whether $\mathrm{NC}^w$ can be simulated by polynomial-size circuits of tree-width $O((\log n)^{w-1})$? As written, the question does not seem to make much sense: for constant $w$, polynomial-size circuits of tree-width $w$ only recognize $\mathrm{NC}^1$ languages (by the result you quote), hence they cannot recognize $\mathrm{NC}^w$ languages for $w\ge2$ unless the NC hierarchy collapses to $\mathrm{NC}^1$.
Emil Jeřábek
CC BY-SA 4.0
2021-02-28T13:49:02.210Z
Yes, my bad. Have amended the question.
ckamath
<reference-request><circuit-complexity><treewidth>
Trading treewidth for depth in Boolean circuits
ckamath
# Trading treewidth for depth in Boolean circuits

(Asked by: username_0 on 2021-02-28)

We know that languages defined by (poly-sized) Boolean formulae *equals* [$\mathbf{NC}^1$](https://en.wikipedia.org/wiki/NC_(complexity)): that Boolean formulae can be simulated in $\mathbf{NC}^1$ was shown by Brent/Spira [B,S], and the converse is quite trivial (simply duplicate the circuit whenever there is a ''collision''). A proof can be found, e.g., in [this](https://www.cs.toronto.edu/%7Etoni/Courses/Complexity2015/lectures/lecture7.pdf) lecture note by Pitassi (Theorem 3).

Boolean formulae (since the underlying graph is a binary tree) can be thought of as circuits with [treewidth](https://en.wikipedia.org/wiki/Treewidth) $1$, where treewidth of a circuit can be defined as the treewidth of the graph obtained by ignoring the direction of the wires. Gal and Jang [GJ] extended the result in [B,S] by showing that a circuit of size $s$ with treewidth $w$ can be simulated in depth $w\log(s)$. *My question is whether the converse is also true*: e.g., whether $\mathbf{NC}^2$ can be simulated using circuits with treewidth $\log(s)$ with only a polynomial blow-up (and more generally, whether $\mathbf{NC}^i$ can be simulated using circuits with treewidth $O(\log^{i-1}(s))$).

Intuitively, this should hold (by following the tree decomposition and then using the duplicating trick). But I could not find any resource regarding this (which makes me wonder whether it is false and there is a blow-up in some step). Any pointers would be appreciated!

[B]: Brent, *The Parallel Evaluation of General Arithmetic Expressions*. Journal of the ACM, 1974.

[GJ]: Gàl and Jang, *A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators*, Inf. Comput., 2016.

[S]: Spira, *On time-hardware complexity tradeoffs for Boolean functions*. Hawaii Symp. on System Sciences, 1971.

**Tags:** reference-request, circuit-complexity, treewidth
> **Comments:**
> **username_1**: Did you mean to ask whether $\mathrm{NC}^w$ can be simulated by polynomial-size circuits of tree-width $O((\log n)^{w-1})$? As written, the question does not seem to make much sense: for constant $w$, polynomial-size circuits of tree-width $w$ only recognize $\mathrm{NC}^1$ languages (by the result you quote), hence they cannot recognize $\mathrm{NC}^w$ languages for $w\ge2$ unless the NC hierarchy collapses to $\mathrm{NC}^1$.  
> **username_0**: Yes, my bad. Have amended the question.  

---

## 0 answers

