11
$\begingroup$

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.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ About 1). Polylog-wise independence is definitely sufficient to fool $AC^{0}$ because of Braverman's breakthrough, but why do you claim it is necessary? $\endgroup$ – Alessandro Cosentino Mar 7 '13 at 10:19
  • $\begingroup$ Actually, I am not sure if I have ever seen a formal mention of 1.) in any paper etc. but I believe this is known. Check out comment 29 by Scott Aaronson here: scottaaronson.com/blog/?p=381 $\endgroup$ – user1694 Mar 7 '13 at 11:10
  • 2
    $\begingroup$ I think the correct statement should be that if you want to fool AC0 by k-wise independence, then $k = polylog(n)$ is necessary. It doesn't say any PRG is like that. $\endgroup$ – Mahdi Cheraghchi Mar 7 '13 at 14:04
  • 1
    $\begingroup$ ok, makes sense now. Another clarification: does the expression "techniques to derandomize other than PRGs" make sense? Isn't a PRG by definition (at least in complexity theory) something that we use to derandomize? @AbhishekBhrushundi: btw, I like the question. It's good to clarify this kind of things on cstheory ;-) $\endgroup$ – Alessandro Cosentino Mar 7 '13 at 14:12
15
$\begingroup$

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

Improve this answer
$\endgroup$
8
$\begingroup$

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}$.

Improve this answer
$\endgroup$

Your Answer

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