Poly-logarithmic independence fools bounded depth circuits
1. Boolean circuits
It is a model of computation. Use AND, NOT and OR gates only. They suffice to compute any Boolean function , but this requires exponential size circuits. We stick to polynomial size circuits, of bounded depth, i.e. the number of gates encountered from each input to output is bounded. This class is called . This models computation that can be performed in constant time.
Example 1 The addition of two integers is in , but their multiplication is not.
Multiplication reduces to Parity, this is why it is not in .
Proof: (Uneasy). If one restricts to a vast majority of inputs of a bounded depth circuit, with high probability nothing remains of the circuit (computes constant function). But parity still varies.
2. -wise independent distributions
Definition 2 A distribution on is -wise independent if its restriction to any coordinates is uniform.
Example 2 Let be uniform and mod . This is a -wise independant distribution.
This example, confronted with Theorem 1, indicates that non local dependence should be invisible to .
Problem 1: What looks random to circuits ?
Today, we focus on a subproblem.
Problem 2: For which do -wise independent distributions look random to circuits, i.e.
The parameters of the problem are number of inputs, size of circuit, depth of circuit, error, degree of independence. We should not expect . Indeed, our circuits can compute every Boolean function on variables, so are able to detect -wise dependence.
A similar argument gives , (indeed, Parity can be computed by a depth circuit of size ).
In 1990, Linial and Nisan conjectured that is sufficient.
In 2007, Bazzi proved it for depth . Simplified proof by Razborov in 2008.
Theorem 3 is sufficient.
Proof: Approximation by polynomials. 1. Low degree polynomials are unsensitive to partial dependence. 2. Show that if is computable by a bounded depth circuit, then is close to a low degree polynomial .
1. If is a degree monomial,
since involves at most variables.
2. Given , find degree polynomials , such that
By LP duality, the search for sandwiching polynomials is in fact equivalent to the original problem.
2.1. Approximation by polynomials
So if ,
2.2. Proof of Theorem 5
By induction on depth. Assume is the AND of functions which we can approximate by Let be a random subset of , where each element is kept with probability . Let be samples, , with of them of each size , . Let
If all are , then , Since we have a large supply of sets of each size, one of them will adjust to the size of .
2.3. Our proof
- If , then .
Then and .
The key observation is that the set of where can be computed by a bounded depth circuit. More precisely, the set of where the construction in the proof of Theorem 5 fails. Its characteristic function can be approximated by a low degree polynomial.