Title: Braverman's proof of the Linial-Nisan Conjecture

Speaker:  Elad Verbin
ITCS, Tsinghua University, China


Date: Friday, February 13, 2009
Time 11:00-11:50
Venue: Room 3464, HKUST

Abstract: 
In this talk I will present the very recent proof of the Linial-Nisan
conjecture, which states that AC0 is fooled by polylog(n)-wise
independence. This conjecture has been open since 1990, and has just
been resolved by Braverman three weeks ago.

Let C be a class of functions from {0,1}^n to {0,1}. Let D be some
distribution over {0,1}^n. We say that D epsilon-fools C if for each
function f in C, it holds that |PR_U (f(x)=1)-PR_D (f(x)=1)|<=epsilon,
where PR_U (f(x)=1) denotes the probability that f(x)=1 where x is
drawn from the uniform distribution, and likewise for PR_D (f(x)=1).
In other words, we want any function in the class to have the almost
the same expectation over D as it has over U. If we can construct such
D deterministically such that D has small support, then we can reduce
the number of bits used in computation, and perhaps even derandomize
some complexity classes. For example, is we can fool any read-once
poly-width branching program to within eps=1/poly using a distribution
with support of size poly(n), then we can get L=RL, which is a major
open problem.

It is easy to see that for any C and epsilon, there exist D with
support of size s=poly(log |C|, 1/epsilon) that epsilon-fools C. To
get such D, we just choose a set S of cardinality s at random and make
D uniform on S. However, this defeats the goal, since to derandomize
anything, we need the construction of D itself to be deterministic.
This is the goal of many works in derandomization theory: to construct
such D with small support, in a deterministic way.

AC0 is the class of functions computable by a constant-depth poly-size
circuit with AND, OR and NOT gates, where the AND and OR gates are
allowed unbounded fan-in. Some weaknesses of such circuits are known.
For example, it is known that such circuits cannot compute the parity
function on n bits. There are two very different proofs for this fact:
one by Hastad (the influence-based approach) and the other by
Razborov-Smolensky (the algebra-based approach).

A distribution D is called k-wise independent if when we restrict to
any k of its coordinates, D looks exactly like the uniform
distribution. Such D can be constructed which has support of size
2^polylog(n), allowing us to sample D with polylog(n) truly random
bits. Braverman proved theor conjecture, and as a consequence gave the
first proof that a general wide class of distributions fools AC0, or
any similarly-powerful class. Note that we already knew from Nisan and
Wigderson's work of a distribution with support of size 2^polylog(n)
that fools AC0, so the novelty in Braverman's work is the fact that he
proves that any k-wise independent distribution works. His result
seems to further our understanding about pseudorandomness.

Braverman's result is based on ideas introduced in Bazzi'a paper from
last year (which showed how to fool DNF using log-wise independence)
and its simplification by Razborov. Interestingly, Braverman's result
critically uses _both_ of the ways to deal with AC0: the
influence-based approach and the algebraic approach, and using both of
them together with some more machinery allows him to prove the
conjecture.

This talk will be self-contained. Braverman's paper is available at:
http://www.cs.toronto.edu/~mbraverm/FoolAC0v6.pdf . For more
information see e.g. Scot Aaronsson's blog:
http://scottaaronson.com/blog/?m=200901 .