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

is small.

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

and

where the expectation in (4) is taken under the uniform distribution. Then it is easy to see that if is -wise independent, then

and

so that

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.

## 3 comments

Comments feed for this article

January 23, 2009 at 3:01 am

News « Combinatorics and more[…] I just saw in “Shtetl Optimized” that the Linial-Nisan conjecture regarding circuits have been proved by Mark Braverman. Scott’s post describes the conjecture as well as related open problem in computational complexity. After many years of no news the case of depth two circuits was proved by Louay Bazzi about a year ago and a simpler proof was found by Razborov. Here is a post on the depth two case from “In theory“. […]

January 23, 2009 at 2:25 pm

Bounded Independence, AC0, and Random 3SAT « in theory[…] depth-2 case was settled only recently by Bazzi, with a proof that, as you may remember, has been significantly simplified by Razborov about six months […]

December 21, 2009 at 3:15 pm

Small-bias Distributions and DNFs « in theory[…] discussed in a previous post, Razborov significantly simplified Bazzi’s proof, retaining the same quantitative […]