CSAIL Event Calendar: Previous Series

Poly-logarithmic Independence Fools AC0 Circuits

Speaker: Mark Braverman , Microsoft Research New England
Date: March 17 2009
Time: 4:15PM to 5:15PM
Location: 32-155
Host: Scott Aaronson, CSAIL, MIT

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.

See other events that are part of Theory Colloquium 2008/2009

See other events happening in March 2009