9
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – chazisop
    Feb 28, 2019 at 6:35

1 Answer 1

Reset to default
9
$\begingroup$

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).

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ 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) $\endgroup$
    – Sam McGuire
    Feb 27, 2019 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.