# Trading treewidth for depth in Boolean circuits

We know that languages defined by (poly-sized) Boolean formulae equals $$\mathbf{NC}^1$$: 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 lecture note by Pitassi (Theorem 3).

Boolean formulae (since the underlying graph is a binary tree) can be thought of as circuits with 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.

• 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$. Feb 28, 2021 at 12:23
• Yes, my bad. Have amended the question. Feb 28, 2021 at 13:49