<p>A bound on fan-out of input bits and gates will make the size of the circuit linear. Let $k$ be a bound on the fan-out of the gates and inputs. It is a DAG with max out degree bounded by $k$ and max path of length $d$. The number of available wires in each level can increase $k$ times, and the number of available wires at top is $kn$, so the total number of wires in the circuit is at most $kn \sum_{i=0}^d k^i \leq k^{d+1} n$ which is $O(n)$.</p>

<p>Any $\mathsf{AC^0}$ function which requires super-linear size will separate the class of functions with bounded fan-out (applied also to input bits) from $\mathsf{AC^0}$. Here are some examples:</p>

<ol>
<li><p>[CR96]: An $\mathsf{AC^0}$ function that need super-linear size is the <em>$\frac{1}{4}$-approximate selector</em>. A $\frac{1}{4}$-approximate selector is any function whose value is:</p>

<ul>
<li>$0$ whenever the number of $1$s is at most $\frac{n}{4}$, </li>
<li>$1$ whenever the number of $0$s is at most $\frac{n}{4}$, </li>
<li>can be either $0$ or $1$ otherwise.</li>
</ul></li>
<li><p>[Ros08] shows that the $k$-clique has $\mathsf{AC^0}$ functions complexity $n^{\Theta(k)}$ ($n^2$ input bits are possible edges of a graph with $n$ vertices). This gives a super line size lowerbound for $k\gt 2$.</p></li>
<li><p>It is probably possible to generalize the example in 2 can to existence of any nontrivial (requiring more than one bit) fixed induced substructure in a given unordered structure, e.g.: </p>

<ul>
<li>existence of a path of length 2 in a given graph,</li>
<li>$\#_1(x)=2$,</li>
</ul>

<p>since they require super constant number of gates depending on a bit which is not possible in $\mathsf{AC^0_{bf}}$.</p></li>
<li><p>The easiest example is a duplicator gate, i.e. a gate that creates $\omega(1)$ copies of its input bit. This is not possible in $\mathsf{AC^0_{bf}}$ since only $O(1)$ of gates can depend on each input bit.</p></li>
</ol>

<p>Also any $\mathsf{AC^0_{bf}}$ circuit of size $S$ can be turned into a formula of size at most $k^dS$ and therefore has a $\mathsf{AC^0_{bf}}$ formula of size $k^{2d+1}n$ so any function of superlinear $\mathsf{AC^0}$ formula complexity will not be in $\mathsf{AC^0_{bf}}$.</p>

<hr>

<p>References: </p>

<p>[CR96] S. Chaudhuri and J. Radhakrishnan, "<a href="http://doi.acm.org/10.1145/237814.237824">Deterministic Restrictions in Circuit Complexity</a>", 1996</p>

<p>[Ros08] Benjamin Rossman, "<a href="http://www.mit.edu/~brossman/k-clique-stoc.pdf">On the Constant-Depth Complexity of k-Clique</a>", 2008</p>

<p>[Juk] Stasys Jukna, "<a href="http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/index.html">Boolean Function Complexity: Advances and Frontiers</a>", draft</p>

CC BY-SA 3.0
2011-07-21T08:39:23.030Z
I updated the answer, thanks to Alessandro, domotorp, Robin, Srikanth, and Stasys.
Kaveh
CC BY-SA 3.0
2011-07-21T13:34:47.887Z
@Kaveh: Example 4 feels a bit like cheating. Although the OP didn't specify, I think he meant to consider classes of decision problems. I think Example 3 is really interesting.. is it obvious that checking if the input's Hamming weight = 2 cannot be done in $AC^0_{bf}$?
Robin Kothari
CC BY-SA 3.0
2011-07-21T13:57:38.867Z
@Robin: I agree about 4, but I think it makes the restriction on the class clear. About 3, no, I don't have a worked out proof right now (I think both ideas from approximate-selector or Ben's sensitivity technique can _probably_ work here).
Kaveh
CC BY-SA 3.0
2011-07-22T02:30:09.500Z
@Kaveh: I don't see why 8-clique requires formulas larger than $n^2$. I know it requires large $AC^0$ circuits, but I'm looking for formula size lower bounds. The formula can have arbitrary depth. In particular we know that Parity is not in $AC^0$, but Parity does have a formula of size $O(n^2)$.
Robin Kothari
CC BY-SA 3.0
2011-07-22T02:34:52.690Z
@RobinKothari: you are right, I forgot that you are looking bounds for general formulas. (I removed my comment).
Kaveh
CC BY-SA 3.0
2011-07-22T02:35:27.963Z
@RobinKothari: I just checked Ben's paper again to see if it is easy to adopt his proof. Generalizing his results does not seem to be straightforward but I think it is possible, at least for some structure like $P_k$.
Kaveh
CC BY-SA 3.0
2011-07-22T14:43:43.487Z
@Kaveh: Alright, thanks. If you do find a way to tweak Rossman's result, I'll be interested to hear it. As for the threshold-2 function, I think we can show it's not in this class by noting that all functions in this class have linear-sized formulae, and threshold-2 has a formula size lower bound of $\Omega(n \log n)$.
Robin Kothari
CC BY-SA 3.0
2011-07-22T15:01:00.057Z
@RobinKothari: I'll post if I manage to tweak it. About threshold-2: good observation.
Kaveh
CC BY-SA 3.0
2011-08-05T07:03:56.637Z
@Kaveh: If by $P_k$, you mean the path of length $k$, you should keep in mind that there are $AC^0$ circuits of size $2^kn^{O(1)}$ for these functions (this follows essentially from the Color Coding technique of Alon, Yuster, and Zwick). I am not sure Rossman's technique gives these sorts of bounds (though I don't know of any reason why it shouldn't).
Srikanth
CC BY-SA 3.0
2011-08-05T10:40:41.080Z
@Srikanth: thanks, I guess you mean [this paper](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.103.5167). I haven't read it carefully, but it doesn't seem to say anything about $\mathsf{AC^0}$. Do you know any other reference that I can check?
Kaveh
CC BY-SA 3.0
2011-08-06T01:45:52.633Z
@Kaveh: I am sorry, I should have provided a reference. The paper you point out initiated the Color coding method for finding paths and other subgraphs quickly. Amano, in [this](http://www.cs.gunma-u.ac.jp/~amano/paper/k_iso.pdf) paper, was the first to point out that the algorithms could be implemented in $AC^0$.
Srikanth
CC BY-SA 3.0
2011-08-06T05:30:31.177Z
@Srikanth: thanks :), although the class of circuits we are talking about are weaker and what I wrote may still be correct, this paper looks very interesting, I will check it. (I couldn't see how the derandomization part could be carried out in $\mathsf{AC^0}$.)
Kaveh
CC BY-SA 2.5
2010-10-01T06:03:39.123Z
A more recent separation between $LC^0$ and $AC^0$ follows from [this result](http://www.mit.edu/~brossman/k-clique-stoc.pdf) due to Benjamin Rossman. He shows that for all constant $k$ (also some growing $k$) and constant $d$, any depth $d$ circuit for $k$-clique on an $n$ vertex graph must have size $\Omega(n^{k/4})$. This implies that the hierarchy of languages accepted by $AC^0$ circuits of size $n^k$ (for different $k$) is actually infinite.
Srikanth
CC BY-SA 3.0
2010-10-01T00:46:57.237Z
2011-07-21T08:37:28.427Z
2011-07-21T08:37:28.427Z
Kaveh
<p>In the survey <a href="http://portal.acm.org/citation.cfm?id=1272729.1272739">"Small Depth Quantum Circuits" by D. Bera, F. Green and S. Homer (p. 36 of ACM SIGACT News, June 2007 vol. 38, no. 2)</a>, I read the following sentence:</p>

<blockquote>
  <p>The classical version of $QAC^0$ (in which $AND$ and $OR$ gates have at most constant fanout) is provably weaker than $AC^0$.</p>
</blockquote>

<p>A reference for this claim is missing. I will call this class $AC^0_{bf}$, where $bf$ stands for "bounded fanout". (The Complexity Zoo is down and I can't verify if such class has already a name in the literature).
If we assume unbounded fanout for the input bits, then these circuit seem to be equivalent to constant depth formulae up to a polynomial increase in the size, so the above claim doesn't make sense. 
Instead, if we assume bounded fanout for the input bits too, then I cannot think of any language that separates this class from $AC^0$. A possible candidate could be the language $X := \{x | \mbox{weight}(x) = 1 \}$, <em>i.e.</em>, the language of the strings with only one 1. It is easy to show $X \in AC^{0}$, but I didn't manage to prove that $X \notin AC^{0}_{bf}$. </p>

<p>The questions are:</p>

<blockquote>
  <p>Is $AC^0_{bf}$ actually weaker than $AC^0$? If it is, any idea or any reference on how to prove it? And what is a language that separates those two classes? What about $X$?</p>
</blockquote>

CC BY-SA 3.0
2011-07-20T07:04:02.940Z
As discussed at follow-up question http://cstheory.stackexchange.com/questions/7447/parity-notin-ac0-with-bounded-fanout-easy-proof, $AC^0_{bf}$ is the same as linear size formula.
domotorp
CC BY-SA 2.5
2010-09-30T17:58:39.000Z
Bounding fan-out of input bits will make the circuit of linear size. Any $AC^0$ function which requires super-linear size will separate them.
Kaveh
CC BY-SA 2.5
2010-09-30T19:43:32.003Z
@Kaveh: Maybe you could repost that as an answer, with perhaps an example of an explicit function which requires super-linear size $AC^0$ circuits and maybe a reference that shows the size lower bound? (Or include the argument in your answer if it is very simple?)
Robin Kothari
CC BY-SA 2.5
2010-09-30T19:50:52.977Z
@Kaveh Thank you. I didn't know that the separation between $AC^0$ and linear size constant-depth circuits (apparently called $LC^0$) was known. The reference is "Deterministic Restrictions in Circuit Complexity" by S. Chaudhuri and J. Radhakrishnan. @Kaveh Can you make your comment an answer?
Alessandro Cosentino
<cc.complexity-theory><circuit-complexity>
Is $AC^0$ with bounded fanout weaker than $AC^0$?
Alessandro Cosentino
# Is $AC^0$ with bounded fanout weaker than $AC^0$?

(Asked by: username_0 on 2010-09-30)

In the survey ["Small Depth Quantum Circuits" by D. Bera, F. Green and S. Homer (p. 36 of ACM SIGACT News, June 2007 vol. 38, no. 2)](http://portal.acm.org/citation.cfm?id=1272729.1272739), I read the following sentence:

> The classical version of $QAC^0$ (in which $AND$ and $OR$ gates have at most constant fanout) is provably weaker than $AC^0$.

A reference for this claim is missing. I will call this class $AC^0\_{bf}$, where $bf$ stands for "bounded fanout". (The Complexity Zoo is down and I can't verify if such class has already a name in the literature).
If we assume unbounded fanout for the input bits, then these circuit seem to be equivalent to constant depth formulae up to a polynomial increase in the size, so the above claim doesn't make sense.
Instead, if we assume bounded fanout for the input bits too, then I cannot think of any language that separates this class from $AC^0$. A possible candidate could be the language $X := \{x | \mbox{weight}(x) = 1 \}$, *i.e.*, the language of the strings with only one 1. It is easy to show $X \in AC^{0}$, but I didn't manage to prove that $X \notin AC^{0}\_{bf}$.

The questions are:

> Is $AC^0\_{bf}$ actually weaker than $AC^0$? If it is, any idea or any reference on how to prove it? And what is a language that separates those two classes? What about $X$?

**Tags:** cc.complexity-theory, circuit-complexity
> **Comments:**
> **username_2**: Bounding fan-out of input bits will make the circuit of linear size. Any $AC^0$ function which requires super-linear size will separate them.  
> **username_3**: @Kaveh: Maybe you could repost that as an answer, with perhaps an example of an explicit function which requires super-linear size $AC^0$ circuits and maybe a reference that shows the size lower bound? (Or include the argument in your answer if it is very simple?)  
> **username_0**: @Kaveh Thank you. I didn't know that the separation between $AC^0$ and linear size constant-depth circuits (apparently called $LC^0$) was known. The reference is "Deterministic Restrictions in Circuit Complexity" by S. Chaudhuri and J. Radhakrishnan. @Kaveh Can you make your comment an answer?  
> **username_1**: As discussed at follow-up question http://cstheory.stackexchange.com/questions/7447/parity-notin-ac0-with-bounded-fanout-easy-proof, $AC^0_{bf}$ is the same as linear size formula.  

---

## 1 answers

### Answer by username_2 on 2010-10-01. Score: 23 | Accepted answer

A bound on fan-out of input bits and gates will make the size of the circuit linear. Let $k$ be a bound on the fan-out of the gates and inputs. It is a DAG with max out degree bounded by $k$ and max path of length $d$. The number of available wires in each level can increase $k$ times, and the number of available wires at top is $kn$, so the total number of wires in the circuit is at most $kn \sum\_{i=0}^d k^i \leq k^{d+1} n$ which is $O(n)$.

Any $\mathsf{AC^0}$ function which requires super-linear size will separate the class of functions with bounded fan-out (applied also to input bits) from $\mathsf{AC^0}$. Here are some examples:

1. [CR96]: An $\mathsf{AC^0}$ function that need super-linear size is the *$\frac{1}{4}$-approximate selector*. A $\frac{1}{4}$-approximate selector is any function whose value is:

   * $0$ whenever the number of $1$s is at most $\frac{n}{4}$,
   * $1$ whenever the number of $0$s is at most $\frac{n}{4}$,
   * can be either $0$ or $1$ otherwise.
2. [Ros08] shows that the $k$-clique has $\mathsf{AC^0}$ functions complexity $n^{\Theta(k)}$ ($n^2$ input bits are possible edges of a graph with $n$ vertices). This gives a super line size lowerbound for $k\gt 2$.
3. It is probably possible to generalize the example in 2 can to existence of any nontrivial (requiring more than one bit) fixed induced substructure in a given unordered structure, e.g.:

   * existence of a path of length 2 in a given graph,
   * $\#\_1(x)=2$,

   since they require super constant number of gates depending on a bit which is not possible in $\mathsf{AC^0\_{bf}}$.
4. The easiest example is a duplicator gate, i.e. a gate that creates $\omega(1)$ copies of its input bit. This is not possible in $\mathsf{AC^0\_{bf}}$ since only $O(1)$ of gates can depend on each input bit.

Also any $\mathsf{AC^0\_{bf}}$ circuit of size $S$ can be turned into a formula of size at most $k^dS$ and therefore has a $\mathsf{AC^0\_{bf}}$ formula of size $k^{2d+1}n$ so any function of superlinear $\mathsf{AC^0}$ formula complexity will not be in $\mathsf{AC^0\_{bf}}$.

---

References:

[CR96] S. Chaudhuri and J. Radhakrishnan, "[Deterministic Restrictions in Circuit Complexity](http://doi.acm.org/10.1145/237814.237824)", 1996

[Ros08] Benjamin Rossman, "[On the Constant-Depth Complexity of k-Clique](http://www.mit.edu/~brossman/k-clique-stoc.pdf)", 2008

[Juk] Stasys Jukna, "[Boolean Function Complexity: Advances and Frontiers](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/index.html)", draft

> **Comments:**
> **username_4**: A more recent separation between $LC^0$ and $AC^0$ follows from [this result](http://www.mit.edu/~brossman/k-clique-stoc.pdf) due to Benjamin Rossman. He shows that for all constant $k$ (also some growing $k$) and constant $d$, any depth $d$ circuit for $k$-clique on an $n$ vertex graph must have size $\Omega(n^{k/4})$. This implies that the hierarchy of languages accepted by $AC^0$ circuits of size $n^k$ (for different $k$) is actually infinite.  
> **username_2**: I updated the answer, thanks to Alessandro, domotorp, Robin, Srikanth, and Stasys.  
> **username_3**: @Kaveh: Example 4 feels a bit like cheating. Although the OP didn't specify, I think he meant to consider classes of decision problems. I think Example 3 is really interesting.. is it obvious that checking if the input's Hamming weight = 2 cannot be done in $AC^0_{bf}$?  
> **username_2**: @Robin: I agree about 4, but I think it makes the restriction on the class clear. About 3, no, I don't have a worked out proof right now (I think both ideas from approximate-selector or Ben's sensitivity technique can _probably_ work here).  
> **username_3**: @Kaveh: I don't see why 8-clique requires formulas larger than $n^2$. I know it requires large $AC^0$ circuits, but I'm looking for formula size lower bounds. The formula can have arbitrary depth. In particular we know that Parity is not in $AC^0$, but Parity does have a formula of size $O(n^2)$.  
> **username_2**: @RobinKothari: you are right, I forgot that you are looking bounds for general formulas. (I removed my comment).  
> **username_2**: @RobinKothari: I just checked Ben's paper again to see if it is easy to adopt his proof. Generalizing his results does not seem to be straightforward but I think it is possible, at least for some structure like $P_k$.  
> **username_3**: @Kaveh: Alright, thanks. If you do find a way to tweak Rossman's result, I'll be interested to hear it. As for the threshold-2 function, I think we can show it's not in this class by noting that all functions in this class have linear-sized formulae, and threshold-2 has a formula size lower bound of $\Omega(n \log n)$.  
> **username_2**: @RobinKothari: I'll post if I manage to tweak it. About threshold-2: good observation.  
> **username_4**: @Kaveh: If by $P_k$, you mean the path of length $k$, you should keep in mind that there are $AC^0$ circuits of size $2^kn^{O(1)}$ for these functions (this follows essentially from the Color Coding technique of Alon, Yuster, and Zwick). I am not sure Rossman's technique gives these sorts of bounds (though I don't know of any reason why it shouldn't).  
> **username_2**: @Srikanth: thanks, I guess you mean [this paper](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.103.5167). I haven't read it carefully, but it doesn't seem to say anything about $\mathsf{AC^0}$. Do you know any other reference that I can check?  
> **username_4**: @Kaveh: I am sorry, I should have provided a reference. The paper you point out initiated the Color coding method for finding paths and other subgraphs quickly. Amano, in [this](http://www.cs.gunma-u.ac.jp/~amano/paper/k_iso.pdf) paper, was the first to point out that the algorithms could be implemented in $AC^0$.  
> **username_2**: @Srikanth: thanks :), although the class of circuits we are talking about are weaker and what I wrote may still be correct, this paper looks very interesting, I will check it. (I couldn't see how the derandomization part could be carried out in $\mathsf{AC^0}$.)  

---

