Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
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
show 4 more comments

1 Answer 1

What you ask for should have bad consequences but I cannot think of any immediately. So I have only some pointers to what we know.

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.

share|improve this answer
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
Unfortunately, nothing. I was thinking of some of the old papers by Buhrman/Homer and others but don't remember anything of this sort. Will get back if something turns up. –  V Vinay Oct 28 '11 at 13:22
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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