Doi: 10.1145/1924421.1924446
Poly-logarithmic Independence
Fools Bounded-Depth
Boolean Circuits
1. intRoDuCtion
The question of determining which (weak) forms of randomness “fool” (or seem totally random to) a given algorithm is
a basic and fundamental question in the modern theory of
computer science. In this work we report progress on this
question by showing that any “k-wise independent” collection of random bits, for some k = (log n)O( 1), fool algorithms
computable by bounded depth circuits. In the process we
also present known tight connections between bounded-depth circuits and low-degree multivariate polynomials. We
establish a new such connection to prove our main result.
In the rest of this section, we introduce the basic concepts
in greater detail so as to present a precise version of our main
result.
1. 1 Bounded depth circuits
A boolean circuit C is a circuit that is comprised of boolean inputs, boolean outputs, and gates that perform operations on the intermediate values within the circuit. The
circuit is not allowed to have loops. In other words, the
gates of the circuit form a directed acyclic graph. A circuit
C with n input bits and one output naturally gives rise to
a boolean function FC: {0, 1}n → {0, 1}. Depending on the
type of the circuit, various restrictions may be placed on
the size of the circuit, its shape, and the types of gates that
it may use. In this paper, we will focus on circuits where
unbounded fan-in AND and OR gates, as well as NOT
gates are allowed.
Since any given circuit accepts a fixed number n of inputs,
it can only compute a function over the set {0, 1}n of strings
of length n. If we want to discuss computing a function F:
{0, 1}* → {0, 1} that takes strings of arbitrary length using
circuits, we need to consider families of circuits parameter-ized by input size. A family of circuits {Cn}n = 1 computes the
function F if each circuit Cn computes the restriction of F to
strings of length n.
The two most important measures of a circuit’s
“power” are size and depth. Circuit size is the total number of gates used in constructing the circuit. For circuits
with AND, OR, and NOT gates the depth is defined as the
largest number of AND and OR gates a signal needs to traverse from any input to the output. The same measures
can be applied to families of circuits. A family {Cn} is of
polynomial size if the size of each Cn is bounded by nc for
some constant c. Circuit complexity studies the amount of
resources (such as size, depth) required to compute various boolean functions.
In this context, studying circuits of bounded depth—
i.e., using at most a constant d number of layers—is of particular interest. The complexity class capturing functions
computed by boolean circuits of bounded depth and polynomial size is denoted by Ac0. Thus Ac0 captures what can
be computed by polynomial size circuits in constant time.
The class Ac0 has been studied extensively in the past three
decades.
There are several reasons why Ac0 circuits have been
studied so extensively. Firstly, Ac0 is essentially the only
class of circuits for which strong unconditional lower-bounds have been proved: it is known, for example, that any
Ac0 circuit computing the parity function PARITY (x1, . . . , xn)
= mod 2 must be of size exponential in n.
5, 6 Secondly,
there is a very tight connection between computations performed by the polynomial hierarchy (Ph) complexity class
relative to an oracle and computations by Ac0 circuits. Thus
better understanding of Ac0 translates into a better understanding of the polynomial hierarchy. Finally, the class of Ac0
functions, and its subclass of DNF formulas has been the target of numerous efficient machine learning algorithms. It is
actually because Ac0 is a relatively weak class that functions in
this class are amenable to efficient learning: it can be shown
that learning functions from larger circuit complexity classes
would allow one to break cryptographic primitives such as
integer factoring.
1. 2 Pseudorandomness: fooling bounded
depth circuits
Randomness is one of the most important computational
resources. A randomized algorithm A may make use of a
string of random bits r Î {0, 1}n as part of the computation.
The randomness may be used, for example, for Monte Carlo
simulations, or for generating random hashes. Denote by
U = U{0, 1}n the uniform distribution on boolean strings of
length n. Then our randomized algorithm A is executed
with r being sampled from U. In reality, truly random
samples are virtually impossible to obtain, and we resort
to pseudorandom distributions and functions that generate
pseudorandom bits, such as the rand function in C. What
makes a distribution m over n-bit strings pseudorandom?
Turns out that the answer to this question depends on the
A previous version of this paper appeared in Proceedings
of the IEEE Conference on Computational Complexity (2009)
and the Journal of the ACM 57, 5 (2010).