I have a few questions regarding fooling constant depth circuits.
- 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?
- 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.