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.

|cite|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$ – Abhishek Bhrushundi 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$ – MCH 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).

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

|cite|improve this answer
$\endgroup$

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.