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