<p>@Alessandro: I am sorry if I misunderstood your question. But my first impression is that one can transform any depth-d <b>circuit</b> of size $S$ into a depth-d <b>formula</b> (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$ <b>formulas</b> implies a lower bound $S^{1/d}$ for $AC^0$ <b>circuits</b>. So, it is hard to expect easier lower bound proofs for $AC^0$ formulas: in the world of $AC^0$, $d$ is a constant.</p>

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

CC BY-SA 3.0
2011-07-20T19:14:31.623Z
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
CC BY-SA 3.0
2011-07-20T20:21:40.510Z
@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
CC BY-SA 3.0
2011-07-20T20:44:21.423Z
but [that is not true](http://cstheory.stackexchange.com/questions/1824/is-ac0-with-bounded-fanout-weaker-than-ac0), 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
CC BY-SA 3.0
2011-07-20T20:59:48.040Z
@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
CC BY-SA 3.0
2011-07-20T21:03:19.217Z
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
CC BY-SA 3.0
2011-07-20T21:12:12.450Z
@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
CC BY-SA 3.0
2011-07-20T23:51:20.530Z
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
CC BY-SA 3.0
2011-07-21T03:32:56.740Z
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
CC BY-SA 3.0
2011-07-21T10:42:13.473Z
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
CC BY-SA 3.0
2011-07-21T19:56:59.563Z
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
CC BY-SA 3.0
2011-07-22T02:02:48.023Z
@Stasys, Both Adam's and [my question](http://cstheory.stackexchange.com/q/1824/1542) arise from work on the quantum class $QAC^0$, which is defined without a fanout gate.
Alessandro Cosentino
CC BY-SA 3.0
2011-07-22T17:16:57.777Z
@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
CC BY-SA 3.0
2011-07-25T17:30:37.900Z
@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
CC BY-SA 3.0
2011-07-27T13:37:05.967Z
@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
CC BY-SA 3.0
2011-07-27T15:22:44.237Z
@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
CC BY-SA 3.0
2011-07-20T18:45:42.447Z
2011-07-20T18:45:42.447Z
Stasys
<p>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, "<a href="http://www.research.rutgers.edu/~troyjlee/parity.pdf" rel="nofollow">The formula size of PARITY</a>", 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}$.</p>

CC BY-SA 3.0
2011-07-19T18:48:20.970Z
so by "Formula" you mean linear size formula, right? and by size you mean formula size...
Alessandro Cosentino
CC BY-SA 3.0
2011-07-20T18:18:42.353Z
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
CC BY-SA 3.0
2011-07-20T20:19:51.857Z
This was exactly what I meant, sorry if my exposition was poor.
domotorp
CC BY-SA 3.0
2011-07-19T18:00:51.947Z
2016-06-23T12:24:52.733Z
2016-06-23T12:24:52.733Z
domotorp
<p>$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.</p>

<p>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 <a href="https://cstheory.stackexchange.com/questions/1824/is-ac0-with-bounded-fanout-weaker-than-ac0">here</a>.  Therefore, PARITY is obviously not in $AC^0_{bf}$.</p>

<p>Is there a proof of PARITY $\notin AC^0_{bf}$ which does <em>not</em> 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?</p>

CC BY-SA 3.0
2011-07-19T17:40:38.693Z
This is called $\mathsf{NC}^0$ in the literature: http://qwiki.stanford.edu/index.php/Complexity_Zoo:N#nc0
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-07-19T17:49:04.973Z
No it is not, as the fanin is unbounded.
domotorp
CC BY-SA 3.0
2011-07-19T18:39:51.017Z
Ah, I misread the word fanout. Thanks for pointing out.
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-07-21T08:52:32.703Z
Related post by @Kaveh: http://cstheory.stackexchange.com/q/1824/1800, moved from the comments below to increase exposure.
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2015-01-27T10:44:36.840Z
What is 'bounded fanout', by the way?
hola
<cc.complexity-theory><circuit-complexity>
PARITY $\notin$ $AC^0$ with bounded fanout: easy proof?
Adam Paetznick
# PARITY $\notin$ $AC^0$ with bounded fanout: easy proof?

(Asked by: username_0 on 2011-07-19)

$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](https://cstheory.stackexchange.com/questions/1824/is-ac0-with-bounded-fanout-weaker-than-ac0). 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?

**Tags:** cc.complexity-theory, circuit-complexity

> **Comments:**
> **username_1**: This is called $\mathsf{NC}^0$ in the literature: http://qwiki.stanford.edu/index.php/Complexity_Zoo:N#nc0  
> **username_2**: No it is not, as the fanin is unbounded.  
> **username_1**: Ah, I misread the word fanout. Thanks for pointing out.  
> **username_1**: Related post by @username_5: http://cstheory.stackexchange.com/q/1824/1800, moved from the comments below to increase exposure.  
> **username_3**: What is 'bounded fanout', by the way?  

---

## 2 answers

### Answer by username_2 on 2011-07-19. Score: 17 | Accepted answer

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](http://www.research.rutgers.edu/~troyjlee/parity.pdf)", 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}$.

> **Comments:**
> **username_7**: so by "Formula" you mean linear size formula, right? and by size you mean formula size...  
> **username_0**: 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.  
> **username_2**: This was exactly what I meant, sorry if my exposition was poor.  

---

### Answer by username_4 on 2011-07-20. Score: 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.

> **Comments:**
> **username_5**: 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.  
> **username_4**: @username_5: 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$.  
> **username_5**: but [that is not true](http://cstheory.stackexchange.com/questions/1824/is-ac0-with-bounded-fanout-weaker-than-ac0), 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.  
> **username_4**: @username_5: 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?  
> **username_5**: 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.  
> **username_4**: @username_5: "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.  
> **username_5**: 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}$.  
> **username_6**: 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}$.  
> **username_4**: 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.  
> **username_4**: 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.  
> **username_7**: @username_4, Both Adam's and [my question](http://cstheory.stackexchange.com/q/1824/1542) arise from work on the quantum class $QAC^0$, which is defined without a fanout gate.  
> **username_4**: @Alessandro: thanks, I don't knew this stuff!  In http://cstheory.stackexchange.com/questions/7156/formula-size-lower-bounds-for-ac0-functions/7211" username_5  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)}$.  
> **username_4**: @Adam: "Is there a proof of $PARITY \not\in AC^0_{bf}$ which does not also go through for $AC^0$?" Now, when username_5 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.  
> **username_0**: @username_4: Indeed this is what username_2 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?  
> **username_4**: @Adam: Thanks, indeed, username_2 already mentioned a non-$AC^0$ argument (Khrapchenko). As http://cstheory.stackexchange.com/questions/1824/is-ac0-with-bounded-fanout-weaker-than-ac0 username_6 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".  

---

