<p>Regarding your last question: The paper <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.3761" rel="nofollow">Size-Depth Trade-offs for Threshold Circuits</a> shows that the parity function requires depth-$d$ threshold circuits with $\ge n^{1+\epsilon(d)}$ wires, which is tight up to the function $\epsilon$.  But for gates not even $\Omega(n)$ lower bounds are known.</p>

CC BY-SA 3.0
2013-12-17T21:09:48.263Z
2013-12-17T21:09:48.263Z
Manu
<p>Not sure about what kind of results you seek but here what I know for sub-classes of $AC^0$ (constant depth and polynomial size Boolean circuits):</p>

<p>The separation between $AC^0$ and its linear fragment (namely $LAC^0$) is known since 96. It is a result of Chaudhuri and Radhakrishnan : "Deterministic restrictions in circuit complexity". This result seems to be non-uniform. </p>

<p>I heard about separation between each layer $n^k$ but unfortunately I don't know any ref for that. </p>

CC BY-SA 3.0
2013-08-19T00:34:32.813Z
2013-08-19T00:34:32.813Z
C.P.
<p>There is the size hierarchy theorem for non-uniform circuits.</p>

<blockquote>
  <p>Do we have any size hierarchy theorem for any kind of uniform circuits ?</p>
</blockquote>

<p>(By uniform here, I mean DLOGTIME uniform. But I don't know if this matters.)</p>

<p>For example, do $O(n)$-size constant depth threshold circuits have less power than the ones with size $O(n^{10})$ or even super-polynomial ?</p>

CC BY-SA 3.0
2013-08-14T15:24:38.460Z
The usual diagonalization argument works.
Kaveh
CC BY-SA 3.0
2013-08-19T04:24:56.750Z
@Kaveh, could you explain what you mean by this? Thanks
Igor Shinkar
CC BY-SA 3.0
2013-08-20T17:34:14.523Z
A slight variant of this question has been asked at http://cstheory.stackexchange.com/questions/5110/hierarchy-theorem-for-circuit-size . Also see a similar question about circuit depth at http://cstheory.stackexchange.com/questions/12872/hierarchy-theorems-for-circuit-depth .
argentpepper
CC BY-SA 3.0
2013-12-17T20:59:12.377Z
@Kaveh, The usual diagonalization argument does not answer (the standard interpretation of) his last question, because you need a function of a fixed depth which cannot be computed by circuits of $O(n)$ size and *any* depth.
Manu
CC BY-SA 3.0
2013-12-17T21:49:52.163Z
@Emanuele, I was not referring to the constant depth part.
Kaveh
CC BY-SA 3.0
2013-12-18T15:10:25.720Z
@Kaveh, it's not clear to me that a simple diagonalization works even for unbounded depth circuits, if you insist on logtime uniformity.
Manu
CC BY-SA 3.0
2013-12-18T20:53:33.447Z
@Emanuele, it is hard to discuss it without particular examples. It seems to me the following works: we need the uniformity of $D(x) = \lnot Eval^C(x,x)$ where $Eval^C$ is the circuit evaluation problem for the circuits in circuit class $C$ (the inputs are promised to be from $C$). Let's say $C$ is $Size(n^k)$. $D(x)$ won't be in $C$. It is not hard to get an upper bound on the size of $D(x)$. The uniformity would follow from the uniformity of $Eval^C$, $x\mapsto (x,x)$, and $\lnot$; and the closure of uniform circuits under composition.
Kaveh
CC BY-SA 3.0
2013-12-18T20:58:39.397Z
If we have a depth restriction then it is more tricky and depends on whether we can show that $Eval^C$ (the eval for an enumeration of functions in the class) can be computed in the required depth. But it works if we also allow a slight increase in depth in addition to size (I think it is reasonable to allow for a diagonal set for $C$ to use more resources of _all_ kinds of restricted resource for the class $C$, e.g. if the class has restriction on time and space it is natural to assume that a diagonal for the class will use _both_ more time and more space than $C$).
Kaveh
<circuit-complexity><uniformity><hierarchy-theorems>
Size hierachy for uniform circuits
Thatchaphol
# Size hierachy for uniform circuits

(Asked by: username_0 on 2013-08-14)

There is the size hierarchy theorem for non-uniform circuits.

> Do we have any size hierarchy theorem for any kind of uniform circuits ?

(By uniform here, I mean DLOGTIME uniform. But I don't know if this matters.)

For example, do $O(n)$-size constant depth threshold circuits have less power than the ones with size $O(n^{10})$ or even super-polynomial ?

**Tags:** circuit-complexity, uniformity, hierarchy-theorems
> **Comments:**
> **username_1**: The usual diagonalization argument works.  
> **username_2**: @Kaveh, could you explain what you mean by this? Thanks  
> **username_3**: A slight variant of this question has been asked at http://cstheory.stackexchange.com/questions/5110/hierarchy-theorem-for-circuit-size . Also see a similar question about circuit depth at http://cstheory.stackexchange.com/questions/12872/hierarchy-theorems-for-circuit-depth .  
> **username_4**: @Kaveh, The usual diagonalization argument does not answer (the standard interpretation of) his last question, because you need a function of a fixed depth which cannot be computed by circuits of $O(n)$ size and *any* depth.  
> **username_1**: @Emanuele, I was not referring to the constant depth part.  
> **username_4**: @Kaveh, it's not clear to me that a simple diagonalization works even for unbounded depth circuits, if you insist on logtime uniformity.  
> **username_1**: @Emanuele, it is hard to discuss it without particular examples. It seems to me the following works: we need the uniformity of $D(x) = \lnot Eval^C(x,x)$ where $Eval^C$ is the circuit evaluation problem for the circuits in circuit class $C$ (the inputs are promised to be from $C$). Let's say $C$ is $Size(n^k)$. $D(x)$ won't be in $C$. It is not hard to get an upper bound on the size of $D(x)$. The uniformity would follow from the uniformity of $Eval^C$, $x\mapsto (x,x)$, and $\lnot$; and the closure of uniform circuits under composition.  
> **username_1**: If we have a depth restriction then it is more tricky and depends on whether we can show that $Eval^C$ (the eval for an enumeration of functions in the class) can be computed in the required depth. But it works if we also allow a slight increase in depth in addition to size (I think it is reasonable to allow for a diagonal set for $C$ to use more resources of _all_ kinds of restricted resource for the class $C$, e.g. if the class has restriction on time and space it is natural to assume that a diagonal for the class will use _both_ more time and more space than $C$).  

---

## 2 answers

### Answer by username_4 on 2013-12-17. Score: 4

Regarding your last question: The paper [Size-Depth Trade-offs for Threshold Circuits](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.3761) shows that the parity function requires depth-$d$ threshold circuits with $\ge n^{1+\epsilon(d)}$ wires, which is tight up to the function $\epsilon$. But for gates not even $\Omega(n)$ lower bounds are known.


---

### Answer by username_5 on 2013-08-19. Score: 3

Not sure about what kind of results you seek but here what I know for sub-classes of $AC^0$ (constant depth and polynomial size Boolean circuits):

The separation between $AC^0$ and its linear fragment (namely $LAC^0$) is known since 96. It is a result of Chaudhuri and Radhakrishnan : "Deterministic restrictions in circuit complexity". This result seems to be non-uniform.

I heard about separation between each layer $n^k$ but unfortunately I don't know any ref for that.


---

