As reported here, here and here, Mark Braverman has just announced a proof of a 1990 conjecture by Linial and Nisan.

Mark proves that if is an AC0 boolean circuit (with NOT gates and with AND gates and OR gates of unbounded fan-in) of depth and size , and if is any -wise independent distribution with , then

that is, “fools” the circuit into thinking that is the uniform distribution over . Plausibly, this might be true even for .

Nothing was known for depth 3 or more, and the 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 ago.

Mark’s proof relies on approximating via low-degree polynomials. The point is that if is an -variate (real valued) polynomial of degree , and is a -wise independent distribution ranging over , then

Now if we could show that approximates both under and under , in the sense that , and also , then we would be done.

The Razborov-Smolenski lower bound technique gives a probabilistic construction of a polynomial such that for every input one has a high probability that . In particular, one get one polynomial such that both

and

Unfortunately this is not sufficient, because the polynomial might be very large at a few points, and so even if agrees with with high probability there is no guarantee that the average of is close to the average of .

Using a result of Linial, Mansour and Nisan (developed in the context of learning theory), one can construct a different kind of low-degree approximating polynomial , which is such that

The Linial-Mansour-Nisan approximation, however, says nothing about the relation between and under the distribution .

Using ideas of Bazzi’s, however, if we had a single polynomial such that properties (1), (2) and (3) are satisfied simultaneously, then we could construct another low-degree polynomial such that , and also , giving us that is fooled by .

As far as I understand, Mark constructs a polynomial satisfying properties (1), (2) and (3) by starting from the Razborov-Smolenski polynomial , and then observing that the indicator function of the points on which is itself a boolean function admitting a Linial-Mansour-Nisan approximation . Defining , we have that has all the required properties, because multiplying by “zeroes out” the points on which is excessively large.

I have been interested in this problem for some time because of a connection with the complexity of 3SAT on random instances.