14
$\begingroup$

$AC^0$ is the class of constant-depth polynomial-size circuits with NOT gates and unbounded fan-in AND and OR gates, where inputs and gates also have unbounded fanout.

Now consider a new class, call it $AC^0_{bf}$ which is like $AC^0$ but for which inputs and gates have fanout at most $O(1)$. This class is clearly in $AC^0$. In fact, it is strictly contained in $AC^0$, as noted here. Therefore, PARITY is obviously not in $AC^0_{bf}$.

Is there a proof of PARITY $\notin AC^0_{bf}$ which does not also go through for $AC^0$? In other words, is there a proof which does not use powerful techniques like the switching lemma or the Razborov/Smolensky method?

Improve this question
$\endgroup$
5

2 Answers 2

Reset to default
17
$\begingroup$

I might miss something, but isn't $AC^0_{bf}$ the same as a Formula? Since every input bit can have an effect on at most a bounded number of gates, we can simply suppose that every gate has only one output (after possibly duplicating a few things) and we can push down not gates as well. We know that the formula size of parity is n^2 (see Troy J. Lee, "The formula size of PARITY", 2007) and since on every level of our circuit we can only have O(n) gates, this shows that parity is not in $AC^0_{bf}$.

Improve this answer
$\endgroup$
3
  • 5
    $\begingroup$ so by "Formula" you mean linear size formula, right? and by size you mean formula size... $\endgroup$
    – Alessandro Cosentino
    Jul 19, 2011 at 18:48
  • 6
    $\begingroup$ I think your answer is correct in the end, but the reasoning is more subtle. Gate fanout can be reduced by duplicating parts of the circuit, but this increases the size of the formula. (Formula size is equivalent to the number of input wires.) Say that the gate fanout is at most 2. Then to reduce the fanout of the bottom layer gates I need to duplicate each gate and each input, doubling the size of the formula. Repeating this process for each layer yields a formula of size $O(2^dn)$ where $d$ is the circuit depth. In our case $d$ is a constant so the formula size is still linear. $\endgroup$
    – Adam Paetznick
    Jul 20, 2011 at 18:18
  • $\begingroup$ This was exactly what I meant, sorry if my exposition was poor. $\endgroup$
    – domotorp
    Jul 20, 2011 at 20:19
4
$\begingroup$

@Alessandro: I am sorry if I misunderstood your question. But my first impression is that one can transform any depth-d circuit of size $S$ into a depth-d formula (fanout 1) of size about $S^d$: just go layer-by-layer starting from the bottom (next to the inputs) layer, and take multiple copies of the same gate; at each layer the number of gates can increase by at most the factor of $S$. This means that any lower bound $S$ for $AC^0$ formulas implies a lower bound $S^{1/d}$ for $AC^0$ circuits. So, it is hard to expect easier lower bound proofs for $AC^0$ formulas: in the world of $AC^0$, $d$ is a constant.

B.t.w. your language $X$ (strings with exactly one $1$) has a trivial DNF (depth-2 formula) with $n$ monomials.

Improve this answer
$\endgroup$
15
  • 3
    $\begingroup$ it seems to me that we can do better than $S^d$ since fan-outs are bounded, we can get $k^dS$ where $k$ is the max fan-out. Moreover, since each input bit is used only bounded number of times, the size of the circuit ($S$) is linear. $\endgroup$
    – Kaveh
    Jul 20, 2011 at 19:14
  • 3
    $\begingroup$ Another way to see that $AC^0_{bf}$ is strictly contained in $AC^0$ is to note that since every input bit has fanout at most k, there are at most $kn$ gates in the first layer, and $k^2n$ gates in the second layer and so on. Since the depth is constant, this means the circuit has $O(n)$ gates in total. Thus any $AC^0$ function that needs super-linear size circuits is not in $AC^0_{bf}$. $\endgroup$
    – Robin Kothari
    Jul 21, 2011 at 3:32
  • 2
    $\begingroup$ Can somebody tell me why this "no more than k copies of an input variable" model is interesting? Even when the depth is constant. In what context such a model arises? Am just curious. $\endgroup$
    – Stasys
    Jul 21, 2011 at 19:56
  • 2
    $\begingroup$ @Stasys, Both Adam's and my question arise from work on the quantum class $QAC^0$, which is defined without a fanout gate. $\endgroup$
    – Alessandro Cosentino
    Jul 22, 2011 at 2:02
  • 3
    $\begingroup$ @Adam: Thanks, indeed, domotorp already mentioned a non-$AC^0$ argument (Khrapchenko). As cstheory.stackexchange.com/questions/1824/… Robin Kothari observed, there is yet another such argument, that of Krichevskii showing that the threshold-2 function needs formulas of size about $n\log n$. Yet better, it is known that all but 16 symmetric Boolean functions require formulas of super-linear size. So, your question is definitely answered with "yes". $\endgroup$
    – Stasys
    Jul 27, 2011 at 15:22

Your Answer

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

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