Is $AC^0$ with bounded fanout weaker than $AC^0$?

Question

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

Answer 1

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", 1996

[Ros08] Benjamin Rossman, "On the Constant-Depth Complexity of k-Clique", 2008

[Juk] Stasys Jukna, "Boolean Function Complexity: Advances and Frontiers", draft