algorithm A. The distribution m is pseudorandom for A, if the behavior of A on samples from m is indistinguishable from its behavior on truly uniformly random r. In particular, if A was likely to work correctly with truly uniform samples, it will be likely to work correctly with samples drawn from m.

For simplicity, suppose that A outputs a single bit. For
a distribution m on length-n strings {0, 1}n, we denote by 0
£ Em[A] £ 1 the expected value of F on inputs drawn accord-
ing to m. When the distribution under consideration is the
uniform distribution U on {0, 1}n, we suppress the subscript
and let E[A] denote the expected value of A. A distribution m
is ε -pseudorandom, or ε-fools A if the expected output when
A is fed samples from m is ε-close to the expected output
when it is fed truly uniform samples:
|Em [A] - E[A]| < ε.

Thus, when we use the rand function in our code, we implicitly hope that its output ε-fools our program.

Similarly to fooling one algorithm, we can define fooling a class of functions. In particular, a distribution m ε-fools Ac0 functions if it ε-fools every function in the class.

The smaller (and weaker) the class of functions is, the easier it is to fool. Since Ac0 is a relatively weak class of functions, there is hope of fooling them using a distribution m or a relatively low entropy. In the late 1980s Nisan10 demonstrated a family of such distributions. In the present paper we will give a very general class of distributions that fool Ac0 circuits, showing that all k-wise independent distributions with k = log O( 1) n fool Ac0 circuits.

1. 3 k-wise independence and the main result A distribution m on {0, 1}n is k-independent if every restriction of m to k coordinates is uniform on {0, 1}k. Clearly, the uniform distribution on {0, 1}n is n-independent. A simple example of a distribution that is (n − 1)-independent but not uniform is

mÅ := (x1, x2, . . . , xn − 1, x1 Å x2 Å . . . Å xn − 1), where the bits x1, . . . , xn − 1 are selected uniformly at random and Å is the XOR operator. Equivalently, mÅ selects a uniformly random string in {0, 1}n subject to the condition that the number of 1’s selected is even.

C⊥ = {x :x ·y = 0 mod 2, ∀y∈C}
gives rise to a k-wise independent distribution. The example
mÅ above corresponds to the n-times repetition code
C = {00 . . . 0, 11. . . 1} whose distance is n, again showing
that mÅ is (n − 1)-wise independent.

2. PRooF oVeRVie W

The main technical ingredient in our work is presenting a new connection between low-degree polynomials and Ac0 circuits. Connections between polynomials and circuits, especially Ac0 circuits, have been explored in the past in various contexts, and remain perhaps the most powerful tool for analyzing these functions.

We begin by observing that k-wise independent distribu-
tions perfectly fool degree-k polynomials. Let m be any k-wise
independent distribution over {0, 1}n. As a first step, let
be a degree-k monomial. m may depend on at
most k different variables, on which m (being k-wise inde-
pendent) appears to be perfectly uniformly random. Thus
Em[m] = E[m].

Now, if f is a degree-k polynomial over x1,..., xn, it can be
written as a sum of degree-k monomials: . Each
monomial is completely fooled by m and thus
( 1)

In light of ( 1), a reasonable attack strategy to prove Theorem 1 would be as follows. For a function F computed by an Ac0 circuit, find a polynomial f that approximates F