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 ?

  • 4
    $\begingroup$ The usual diagonalization argument works. $\endgroup$
    – Kaveh
    Commented Aug 14, 2013 at 15:24
  • 1
    $\begingroup$ @Kaveh, could you explain what you mean by this? Thanks $\endgroup$ Commented Aug 19, 2013 at 4:24
  • 2
    $\begingroup$ 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/… . $\endgroup$ Commented Aug 20, 2013 at 17:34
  • 2
    $\begingroup$ @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. $\endgroup$
    – Manu
    Commented Dec 17, 2013 at 20:59
  • 2
    $\begingroup$ @Kaveh, it's not clear to me that a simple diagonalization works even for unbounded depth circuits, if you insist on logtime uniformity. $\endgroup$
    – Manu
    Commented Dec 18, 2013 at 15:10

2 Answers 2


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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