# Does $\mathsf{P/poly}$ have subexponential-size bounded-depth circuits?

Is there any plausible complexity/crypto hypothesis that rules out the possibility that polynomial size circuits have subexponential-size (i.e. $2^{O(n^\epsilon)}$ with $\epsilon<1$) bounded-depth ($d = O(1)$) circuits?

We know that every function computable by a $\mathsf{NC^1}$ circuit can be computed by a size $2^{O(n^\epsilon)}$ depth $d$ circuit (using AND, OR, and NOT gates, unbounded fan-in) (for every $0 <\epsilon$ there is a $d$ and $d$ can be taken to be $O(1/\epsilon)$).

The question is:

is there a reason that would make the existence of such circuits for general polynomial size circuits unlikely?

• If by subexponential-size you mean $2^{n^{o(1)}}$ (rather than $2^{o(n)}$) and by bounded-depth you mean constant depth, then parity does not have subexponential-sized bounded-depth circuits under no assumptions. – MCH Oct 27 '11 at 18:18
• You should post your comment as an answer. You'll get credit for it, and if appropriate it can be marked as an accepted answer. This will also prevent the question from being automatically reposted periodically by the Community bot. – Suresh Venkat Oct 27 '11 at 18:25
• @MCH, I updated the question to clarify what I mean by subexponential size. – Kaveh Oct 27 '11 at 22:19
• In the uniform case, you can say something ($TIME(t) \subseteq \Sigma_{O(d)}TIME[n^{1/d}]$ implies time lower bounds for SAT). But in the non-uniform case, we know no strong lower bounds for P/poly, and no strong lower bounds for your definition of sub-exponential size constant-depth circuits. E.g. it's still possible $EXP^{NP}$ could be simulated in either of these classes. So I am not sure what you could conclude. (Why did I make this a comment? Because it's not really an answer...) – Ryan Williams Oct 28 '11 at 3:39
• Well, $TIME(t) \subseteq ATIME(t^{1-\epsilon})$ is considered unlikely. Sipser (CCC' 86) showed that either $P = RP$ or $TIME(t) \subseteq SPACE(t^{1-\epsilon})$ for some $\epsilon > 0$, under certain expander construction hypotheses that were later shown to be true by Saks, Srinivasan, and Zhou.This was taken as evidence that $P = RP$. Later work on hardness vs randomness made the connections more precise. – Ryan Williams Nov 11 '11 at 21:42

Check out Viola's On the power of small depth computation The best we know is Valiant's construction for boolean circuits: log depth linear sized circuits to depth 3 subexp circuits. (We know better for arithmetic circuits.) There are also some results of Beigel/Tarui on ACC begin contained in bounded depth circuits of superpoly size. I don't recall it being extended to all of $NC^1$ though.
• Thanks for the interesting pointers. I am mainly interested on the likeliness of the existence of such simulation (i.e. conjectures and hypothesis that would imply a negative or positive answer for $\mathsf{P/poly}$ and similar classes like $\mathsf{NC}$ where the answer is not known unconditionally.) Do we know anything like that? – Kaveh Oct 28 '11 at 11:14