<p>Unfortunately, the best known depth reductions for Boolean circuits only work for very restricted classes of circuits. Valiant (<a href="https://link.springer.com/chapter/10.1007/3-540-08353-7_135" rel="nofollow noreferrer">Valiant</a>; <a href="http://www.ccs.neu.edu/home/viola/papers/shallow.pdf" rel="nofollow noreferrer">Viola</a>) proved that a circuit of size <span class="math-container">$O(n)$</span> and depth <span class="math-container">$O(\log{n})$</span> can be computed by a depth-3 circuit of size <span class="math-container">$2^{O(n/\log\log{n})}$</span>. Also, Valiant showed a similar depth reduction for linear size series-parallel circuits (a natural subclass of circuits), see <a href="http://cseweb.ucsd.edu/~ccalabro/series_parallel.pdf" rel="nofollow noreferrer">Calabro</a>.</p>

<p>Note that the number of gates in a depth-3 circuit computing a random function is <span class="math-container">$\Theta(2^{n/2})$</span> (<a href="https://www.sciencedirect.com/science/article/pii/0020019095001824" rel="nofollow noreferrer">Dančík</a>; <a href="http://www.mathnet.ru/php/archive.phtml?wshow=paper&amp;jrnid=dm&amp;paperid=1449&amp;option_lang=eng" rel="nofollow noreferrer">Sergeev</a>), while the best lower bound we can prove is only <span class="math-container">$2^{\Omega(\sqrt{n})}$</span> (<a href="https://www.nada.kth.se/~johanh/largesmalldepth.pdf" rel="nofollow noreferrer">Håstad</a>; <a href="https://www.computer.org/csdl/proceedings/focs/1993/4370/00/0366875.pdf" rel="nofollow noreferrer">Håstad, Jukna, Pudlák</a>; <a href="https://pdfs.semanticscholar.org/b9bd/fbbc799580938972802ac75132bedf75e0de.pdf" rel="nofollow noreferrer">Paturi, Pudlák, Zane</a>; <a href="https://www.sciencedirect.com/science/article/pii/S0020019097001312" rel="nofollow noreferrer">Boppana</a>; <a href="http://cseweb.ucsd.edu/~paturi/myPapers/pubs/PaturiPudlakSaksZane_2005_jacm.pdf" rel="nofollow noreferrer">Paturi, Pudlák, Saks, Zane</a>; <a href="http://cs.haifa.ac.il/~ormeir/papers/prediction-with-hindsight.pdf" rel="nofollow noreferrer">Meir, Wigderson</a>).</p>

CC BY-SA 4.0
2019-02-27T21:25:11.810Z
It's worth including as a comment: there are also depth-reduction results for $\mathsf{ACC}^0$ (another very restricted class). Depth-$d$ circuits with AND, OR, NOT or MOD m can be converted to depth-$2$ circuits of the form SYM-AND so that the size is $2^{polylog(n)}$ and the bottom gate fan-in is $polylog(n)$ (via Yao, Beigel-Tarui, Chen-Papakonstantinou)
Sam McGuire
CC BY-SA 4.0
2019-02-26T16:58:49.073Z
2019-02-27T15:45:01.660Z
2019-02-27T15:45:01.660Z
Alex Golovnev
<p>This <a href="https://arxiv.org/abs/1304.5777" rel="noreferrer">result</a> by Tavenas, Koiran and others show that any polynomial computed by a circuit of size <span class="math-container">$s$</span> is computed by a depth-4 homogenous circuit of size <span class="math-container">$s^{\sqrt{d}}$</span>.</p>

<p>Are there any similar results for Boolean circuits or do we know why such a thing is not possible? </p>

CC BY-SA 4.0
2019-02-28T06:35:29.893Z
If I recall correctly, such a result is not possible on the boolean world. I'm having trouble recalling the specific result, I think maybe this is it https://arxiv.org/abs/1504.03398 points towards this direction. I may update this to an answer if I find the actual reference I vaguely recall.
chazisop
<cc.complexity-theory><circuit-complexity><arithmetic-circuits>
Depth reduction for Boolean circuits
Math Learner
# Depth reduction for Boolean circuits

(Asked by: username_0 on 2019-02-25)

This [result](https://arxiv.org/abs/1304.5777) by Tavenas, Koiran and others show that any polynomial computed by a circuit of size $s$ is computed by a depth-4 homogenous circuit of size $s^{\sqrt{d}}$.

Are there any similar results for Boolean circuits or do we know why such a thing is not possible?

**Tags:** cc.complexity-theory, circuit-complexity, arithmetic-circuits

> **Comments:**
> **username_1**: If I recall correctly, such a result is not possible on the boolean world. I'm having trouble recalling the specific result, I think maybe this is it https://arxiv.org/abs/1504.03398 points towards this direction. I may update this to an answer if I find the actual reference I vaguely recall.  

---

## 1 answers

### Answer by username_2 on 2019-02-26. Score: 9

Unfortunately, the best known depth reductions for Boolean circuits only work for very restricted classes of circuits. Valiant ([Valiant](https://link.springer.com/chapter/10.1007/3-540-08353-7_135); [Viola](http://www.ccs.neu.edu/home/viola/papers/shallow.pdf)) proved that a circuit of size $O(n)$ and depth $O(\log{n})$ can be computed by a depth-3 circuit of size $2^{O(n/\log\log{n})}$. Also, Valiant showed a similar depth reduction for linear size series-parallel circuits (a natural subclass of circuits), see [Calabro](http://cseweb.ucsd.edu/~ccalabro/series_parallel.pdf).

Note that the number of gates in a depth-3 circuit computing a random function is $\Theta(2^{n/2})$ ([Dančík](https://www.sciencedirect.com/science/article/pii/0020019095001824); [Sergeev](http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dm&paperid=1449&option_lang=eng)), while the best lower bound we can prove is only $2^{\Omega(\sqrt{n})}$ ([Håstad](https://www.nada.kth.se/~johanh/largesmalldepth.pdf); [Håstad, Jukna, Pudlák](https://www.computer.org/csdl/proceedings/focs/1993/4370/00/0366875.pdf); [Paturi, Pudlák, Zane](https://pdfs.semanticscholar.org/b9bd/fbbc799580938972802ac75132bedf75e0de.pdf); [Boppana](https://www.sciencedirect.com/science/article/pii/S0020019097001312); [Paturi, Pudlák, Saks, Zane](http://cseweb.ucsd.edu/~paturi/myPapers/pubs/PaturiPudlakSaksZane_2005_jacm.pdf); [Meir, Wigderson](http://cs.haifa.ac.il/~ormeir/papers/prediction-with-hindsight.pdf)).

> **Comments:**
> **username_3**: It's worth including as a comment: there are also depth-reduction results for $\mathsf{ACC}^0$ (another very restricted class). Depth-$d$ circuits with AND, OR, NOT or MOD m can be converted to depth-$2$ circuits of the form SYM-AND so that the size is $2^{polylog(n)}$ and the bottom gate fan-in is $polylog(n)$ (via Yao, Beigel-Tarui, Chen-Papakonstantinou)  

---

