7

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 ?

Thatchaphol
  • 1,130
  • 8
  • 18
  • 4
    The usual diagonalization argument works. – Kaveh Aug 14 '13 at 15:24
  • 1
    @Kaveh, could you explain what you mean by this? Thanks – Igor Shinkar Aug 19 '13 at 04:24
  • 2
    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 Aug 20 '13 at 17:34
  • 2
    @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
  • 1
    @Emanuele, I was not referring to the constant depth part. – Kaveh Dec 17 '13 at 21:49
  • 2
    @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
  • 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. – Kaveh Dec 18 '13 at 20:53
  • 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 Dec 18 '13 at 20:58

2 Answers2

4

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.

Manu
  • 7,659
  • 3
  • 37
  • 42
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.

C.P.
  • 992
  • 5
  • 12