23
$\begingroup$

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

$\endgroup$
  • 6
    $\begingroup$ 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. $\endgroup$ – Kaveh Sep 30 '10 at 17:58
  • 2
    $\begingroup$ @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?) $\endgroup$ – Robin Kothari Sep 30 '10 at 19:43
  • 2
    $\begingroup$ @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? $\endgroup$ – Alessandro Cosentino Sep 30 '10 at 19:50
  • 2
    $\begingroup$ As discussed at follow-up question cstheory.stackexchange.com/questions/7447/…, $AC^0_{bf}$ is the same as linear size formula. $\endgroup$ – domotorp Jul 20 '11 at 7:04
23
$\begingroup$

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

$\endgroup$
  • 12
    $\begingroup$ A more recent separation between $LC^0$ and $AC^0$ follows from this result 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. $\endgroup$ – Srikanth Oct 1 '10 at 6:03
  • 1
    $\begingroup$ I updated the answer, thanks to Alessandro, domotorp, Robin, Srikanth, and Stasys. $\endgroup$ – Kaveh Jul 21 '11 at 8:39
  • 1
    $\begingroup$ @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)$. $\endgroup$ – Robin Kothari Jul 22 '11 at 14:43
  • 1
    $\begingroup$ @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). $\endgroup$ – Srikanth Aug 5 '11 at 7:03
  • 1
    $\begingroup$ @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 paper, was the first to point out that the algorithms could be implemented in $AC^0$. $\endgroup$ – Srikanth Aug 6 '11 at 1:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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