CSAIL Event Calendar: Previous Series
Poly-logarithmic Independence Fools AC0 Circuits
Speaker: Mark Braverman , Microsoft Research New England
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.