<p>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.</p>

<p>Check out Viola's <a href="http://www.ccs.neu.edu/home/viola/papers/shallow.pdf">On the power of small depth computation</a> 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 <a href="http://www.cse.iitk.ac.in/users/manindra/algebra/depth-four.pdf">arithmetic circuits</a>.) 
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.</p>

CC BY-SA 3.0
2011-10-28T11:14:53.687Z
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
CC BY-SA 3.0
2011-10-28T13:22:25.850Z
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
CC BY-SA 3.0
2011-10-28T02:19:20.623Z
2011-10-28T02:19:20.623Z
V Vinay
<p>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&lt;1$) bounded-depth ($d = O(1)$) circuits?</p>

<p>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 &lt;\epsilon$ there is a $d$ and $d$ can be taken to be $O(1/\epsilon)$). </p>

<p>The question is: </p>

<blockquote>
  <p>is there a reason that would make the existence of such circuits for general polynomial size circuits unlikely?</p>
</blockquote>

CC BY-SA 3.0
2011-10-27T18:18:11.127Z
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.
Mahdi Cheraghchi
CC BY-SA 3.0
2011-10-27T18:25:44.157Z
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
CC BY-SA 3.0
2011-10-27T22:19:18.033Z
@MCH, I updated the question to clarify what I mean by subexponential size.
Kaveh
CC BY-SA 3.0
2011-10-28T03:39:20.087Z
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
CC BY-SA 3.0
2011-10-28T11:09:29.853Z
Thanks @Ryan Williams. So even conditionally it is not known to be unlikely? (Assuming hypotheses like [ETH](http://en.wikipedia.org/wiki/Exponential_time_hypothesis), existence of SPRG, OWP, super-bits, ...)
Kaveh
CC BY-SA 3.0
2011-11-11T21:42:57.770Z
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
CC BY-SA 3.0
2011-11-13T17:32:05.580Z
@Ryan, thank you. I think I understand what you wrote. The result for simulation that I mentioned in the question also works for uniform case, but in the uniform case what I asked is unlikely. So it is also unlikely for nonuniform case unless we use the nonuniformity of the circuits in some essential way.
Kaveh
CC BY-SA 3.0
2013-01-08T17:48:30.383Z
@Ricky, hopefully the question is more clear now.
Kaveh
<cc.complexity-theory><circuit-complexity><bounded-depth>
Does $\mathsf{P/poly}$ have subexponential-size bounded-depth circuits?
Kaveh
# Does $\mathsf{P/poly}$ have subexponential-size bounded-depth circuits?

(Asked by: username_0 on 2011-10-27)

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?

**Tags:** cc.complexity-theory, circuit-complexity, bounded-depth

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_0**: @MCH, I updated the question to clarify what I mean by subexponential size.  
> **username_3**: 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...)  
> **username_0**: Thanks @username_3. So even conditionally it is not known to be unlikely? (Assuming hypotheses like [ETH](http://en.wikipedia.org/wiki/Exponential_time_hypothesis), existence of SPRG, OWP, super-bits, ...)  
> **username_3**: 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.  
> **username_0**: @Ryan, thank you. I think I understand what you wrote. The result for simulation that I mentioned in the question also works for uniform case, but in the uniform case what I asked is unlikely. So it is also unlikely for nonuniform case unless we use the nonuniformity of the circuits in some essential way.  
> **username_0**: @Ricky, hopefully the question is more clear now.  

---

## 1 answers

### Answer by username_4 on 2011-10-28. Score: 9

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](http://www.ccs.neu.edu/home/viola/papers/shallow.pdf) 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](http://www.cse.iitk.ac.in/users/manindra/algebra/depth-four.pdf).)
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.

> **Comments:**
> **username_0**: 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?  
> **username_4**: 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.  

---

