# Depth reduction for Boolean circuits

This result 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?

• 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 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. Feb 28 '19 at 6:35

Unfortunately, the best known depth reductions for Boolean circuits only work for very restricted classes of circuits. Valiant (Valiant; Viola) 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.
Note that the number of gates in a depth-3 circuit computing a random function is $$\Theta(2^{n/2})$$ (Dančík; Sergeev), while the best lower bound we can prove is only $$2^{\Omega(\sqrt{n})}$$ (Håstad; Håstad, Jukna, Pudlák; Paturi, Pudlák, Zane; Boppana; Paturi, Pudlák, Saks, Zane; Meir, Wigderson).
• 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) Feb 27 '19 at 21:25