14

$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?

Community
  • 1
Adam Paetznick
  • 640
  • 4
  • 8

2 Answers2

17

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}$.

Kaveh
  • 21,577
  • 8
  • 82
  • 183
domotorp
  • 13,931
  • 37
  • 93
  • 5
    so by "Formula" you mean linear size formula, right? and by size you mean formula size... – Alessandro Cosentino Jul 19 '11 at 18:48
  • 6
    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. – Adam Paetznick Jul 20 '11 at 18:18
  • This was exactly what I meant, sorry if my exposition was poor. – domotorp Jul 20 '11 at 20:19
4

@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.

Stasys
  • 6,765
  • 29
  • 54
  • 3
    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. – Kaveh Jul 20 '11 at 19:14
  • @Kaveh: I understood that the problem is NOT to reduce a bounded fanout circuit to a formula (fanout 1 circuit). We can do this for unbounded fanout as well. What I wanted to say is that $AC^0_{bf}$ = $AC^0$. – Stasys Jul 20 '11 at 20:21
  • but that is not true, the size of a $\mathsf{AC^0_{bf}}$ circuit is always bounded by $k^dn$, they cannot compute even arbitrary polynomial size sum of monomials since each variable can be used only a constant number of times. A simpler example is the function with $n$ (or any super constant number of) output bits all equal to the first bit of the input, this cannot be computed by constant depth bounded fan-out circuits. – Kaveh Jul 20 '11 at 20:44
  • @Kaveh: cannot believe it. Would like to know why an $AC^0$ circuit of size $S$ cannot be transformed to an $AC^0$ formula of size about $S^d$. Do we speak about some different models? – Stasys Jul 20 '11 at 20:59
  • they can, but the resulting formula won't have bounded fan-out. I guess what you are missing is that inputs are also considered gates here and therefore the fan-out of the inputs are also bounded. In a $\mathsf{AC^0}$ formula this is not the case, variables can be used arbitrary number of times. – Kaveh Jul 20 '11 at 21:03
  • @Kaveh: "In a AC0 formula this is not the case, variables can be used arbitrary number of times.". Yes, but (when going from a circuit to a formula) the first layer will only grow from $S$ to $S^2$. I don't think that the fanout of input literals may be a problem. – Stasys Jul 20 '11 at 21:12
  • 1
    The problem is not the size increase, the problem is that input variables in $\mathsf{AC^0}$ even as formulas can have unbounded fanout, each can be used any number of times whereas in $\mathsf{AC^0_{bf}}$ they can be used only a bounded number of times. If we also consider each input as a gates the formula is not really a tree but is a DAG because of the fanout of the inputs. In $\mathsf{AC^0_{bf}}$ each input variable can have influence only on a bounded number of gates ($k^d$ gates) and its value has no effect on the rest of the gates, but this is not the case in $\mathsf{AC^0}$. – Kaveh Jul 20 '11 at 23:51
  • 3
    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}$. – Robin Kothari Jul 21 '11 at 03:32
  • Well, now I see that you deal with an entirely different model (have never seen it before): you do not allow one input literal to appear as an input-gate many times (as, say is the case in formulas). Indeed, under your restriction all formulas (fanout 1) have O(n) size. – Stasys Jul 21 '11 at 10:42
  • 2
    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. – Stasys Jul 21 '11 at 19:56
  • 2
    @Stasys, Both Adam's and my question arise from work on the quantum class $QAC^0$, which is defined without a fanout gate. – Alessandro Cosentino Jul 22 '11 at 02:02
  • 2
    @Alessandro: thanks, I don't knew this stuff! In http://cstheory.stackexchange.com/questions/7156/formula-size-lower-bounds-for-ac0-functions/7211" Kaveh already listed some proofs of $AC^-_{bf}\neq AC^0$. They all, however, use a not-as-trivial machinery. But there is also an almost trivial argument, the "greedy" one which I sketched in http://cstheory.stackexchange.com/questions/7156/formula-size-lower-bounds-for-ac0-functions/7216#7216. By this argument one can construct a function in $AC^0$ of depth 3 which requires formulas of size $n^{2-o(1)}$. – Stasys Jul 22 '11 at 17:16
  • @Adam: "Is there a proof of $PARITY \not\in AC^0_{bf}$ which does not also go through for $AC^0$?" Now, when Kaveh and Robin explained that $AC^0_{bf}$ has linear-size formulas, this question is answered. Isn't it? The proof of Khrapchenko that parity requires $n^2$ formula size does not imply that parity is not in $AC^0$. Am asking just to fix the status of this your question. – Stasys Jul 25 '11 at 17:30
  • @Stasys: Indeed this is what domotorp explains (with some clarification in the comments) in his answer, which I accepted. Is there something else I need to do to set the status of this question? – Adam Paetznick Jul 27 '11 at 13:37
  • 3
    @Adam: Thanks, indeed, domotorp already mentioned a non-$AC^0$ argument (Khrapchenko). As http://cstheory.stackexchange.com/questions/1824/is-ac0-with-bounded-fanout-weaker-than-ac0 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". – Stasys Jul 27 '11 at 15:22