7
$\begingroup$

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 ?

| cite | improve this question | |
$\endgroup$
  • 4
    $\begingroup$ The usual diagonalization argument works. $\endgroup$ – Kaveh Aug 14 '13 at 15:24
  • 1
    $\begingroup$ @Kaveh, could you explain what you mean by this? Thanks $\endgroup$ – Igor Shinkar Aug 19 '13 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$ – argentpepper Aug 20 '13 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 Dec 17 '13 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 Dec 18 '13 at 15:10
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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