Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
    
This is called $\mathsf{NC}^0$ in the literature: qwiki.stanford.edu/index.php/Complexity_Zoo:N#nc0 –  Hsien-Chih Chang 張顯之 Jul 19 '11 at 17:40
4  
No it is not, as the fanin is unbounded. –  domotorp Jul 19 '11 at 17:49
    
Ah, I misread the word fanout. Thanks for pointing out. –  Hsien-Chih Chang 張顯之 Jul 19 '11 at 18:39
    
Related post by @Kaveh: cstheory.stackexchange.com/q/1824/1800, moved from the comments below to increase exposure. –  Hsien-Chih Chang 張顯之 Jul 21 '11 at 8:52
add comment

2 Answers 2

up vote 15 down vote accepted

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 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.114.7184) 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}$.

share|improve this answer
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
5  
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
add comment

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

share|improve this answer
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
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 3:32
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 2:02
2  
@Adam: Thanks, indeed, domotorp already mentioned a non-$AC^0$ argument (Khrapchenko). As cstheory.stackexchange.com/questions/1824/… 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
show 10 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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