# Size hierachy for uniform circuits

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 ?

• The usual diagonalization argument works. – Kaveh Aug 14 '13 at 15:24
• @Kaveh, could you explain what you mean by this? Thanks – Igor Shinkar Aug 19 '13 at 4:24
• A slight variant of this question has been asked at cstheory.stackexchange.com/questions/5110/… . Also see a similar question about circuit depth at cstheory.stackexchange.com/questions/12872/… . – argentpepper Aug 20 '13 at 17:34
• @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 Dec 17 '13 at 20:59
• @Kaveh, it's not clear to me that a simple diagonalization works even for unbounded depth circuits, if you insist on logtime uniformity. – Manu Dec 18 '13 at 15:10

Regarding your last question: The paper Size-Depth Trade-offs for Threshold Circuits 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.
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.