On fooling $AC^0$

Question

I have a few questions regarding fooling constant depth circuits.

1. It's known that $\log^{O(d)}(n)$-wise independence is necessary to fool $AC^0$ circuits of depth $d$, where $n$ is the size of the input. How can one prove this?
2. Since the above is true, any pseudorandom generator that fools $AC^0$ circuits of depth $d$ must necessarily have seed length $l = \Omega(\log^d(n))$, which would then mean that one cannot expect to prove $RAC^0 = AC^0$ via PRGs. I believe $RAC^0 \stackrel{?}{=} AC^0$ is still an open question, so this means that one has to use techniques other than PRGs to prove $RAC^0 = AC^0$. I find this weird because, at least in the case of $P \stackrel{?}{=} BPP$, we believe that PRGs are essentially the only way to go about answering this question.

I think I am missing something really basic here.

Answer 1

1) What is meant by necessary is that one way to generate a $k$-wise independent distribution is to break the input in blocks of $k+1$ bits, and let the $(k+1)$th bit of each block be the parity of the other $k$ bits in the block. Obviously this distribution can be broken just by computing parity on $k$ bits. The result you claim follows from the fact that poly($n$) circuits of depth $d$ can compute parity on $\log^{d-1} n$ bits.

2) No. 1) is only talking about a specific construction of $k$-wise independent distributions. Conceivably there are $O(\log n)$-seed generators that fool poly-size bounded-depth circuits (this also follows from sufficiently strong lower bounds against bounded-depth circuits, though the standard hardness vs. randomness tradeoffs do not suffice, see e.g. the discussion of a paper by Agrawal in Section 3.2 of http://www.ccs.neu.edu/home/viola/papers/JournalCCC03.pdf).

Answer 2

Polylog independence may not be the only way to fool $AC^{0}$ circuits. To illustrate this example, consider the class of linear polynomials. Any zero set of a linear polynomial is $(n-1)$-wise independent but of course this doesn't fool linear polynomials. Hence, $(n-1)$-wise independent distributions do not fool this class. This of course doesn't mean that only $n$-wise independent distributions fool this class ($\epsilon$-biased spaces fool them, and are polynomial sized spaces).

I guess what one means when they say "$\log^{O(d)} n$-wise independence is necessary" is that there are examples of distributions with smaller independence, and it is known that they do not fool $AC^{0}$.