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