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.