SPECIAL TIME: 2:30 -- 3:30 pm, Monday, Feb 23, 2009

PLACE: Theory Lab, CSE 306.

SPEAKER: Mark Braverman, Microsoft New England

TITLE: Poly-logarithmic Independence Fools AC0 Circuits

ABSTRACT:

We will describe the recent proof of the 1990 Linial-Nisan conjecture.
The conjecture states that bounded-depth boolean circuits cannot
distinguish poly-logarithmically independent distributions from the
uniform one. The talk will be almost completely self-contained.