In 1990, Linial and Nisan conjectured that every AC0 function is “fooled” by polylog-wise independence. This means that if is computed by a circuit of size and depth , and is a distribution over such that every bits are mutually independent and uniformly distributed (such a distribution is called -wise independent), then
where is the uniform distribution over , provided that is around . (Maybe even around .)
Nearly 20 years later, not much is known about this conjecture, except for a breakthrough result by Louay Bazzi from last year. Bazzi proves that (1) holds if is computed by a size- depth-2 circuit (that is, a CNF or a DNF) and is a -wise independent distribution. This settles the depth-2 case of the Linial-Nisan conjecture.
A result of Linial, Mansour and Nisan plays an important role in the proof. The result is that if is computed by a DNF of size , then there is a function that can be written as a degree- polynomial with and that is “close” to , in the sense that
Now, if is a degree- polynomial, and is a -wise independent distribution, we have
and we also have from (2). If we also had , then we would be done.
Unfortunately, we have no way to relate and , because the fact that and are close does not imply that they have similar expectations under the distribution , which could be concentrated on the few inputs on which and are very different.
Although the Linial-Mansour-Nisan result does not immediately give us the desired result, it is intuitive that it is useful to be able to approximate a DNF by low-degree polynomials, and to know that low-degree polynomials are perfectly “fooled” by -wise independent distributions.
Bazzi observes that the following stronger polynomial approximation property is sufficient to prove that a distribution fools a given function.
Suppose that is a function, and that we are able to find two degree- polynomials such that for every we have
where the expectation in (4) is taken under the uniform distribution. Then it is easy to see that if is -wise independent, then
It is also possible to use linear programming duality that argue that if is fooled by -wise independent distributions, then degree- polynomials as above must exist.
Bazzi then shows that, given a size- DNF , it is possible to find degree- polynomials as above with .
Finding such polynomials, in turn, is reduced rather cleverly to the task of finding a single polynomial such that is small, as in Linial-Mansour-Nisan and, in addition, has the property that whenever then we always must have .
The construction of this “one sided” low-degree approximation of is the bulk of Bazzi’s paper. A couple of days ago, Razborov has posted an exceedingly neat construction, that he explains in a page and a half! (Theorem 7 in the link above.)
It is rather appropriate that this has happened during the Banff Workshop on Analytic Tools in Computational Complexity, and tomorrow Scott Aaronson will give an impromptu talk on Razborov’s proof, hot from the presses.