Eastern Great Lakes Theory Workshop Talk

Poly-logarithmic Independence Fools AC₀ Circuits

Mark Braverman, Microsoft Research

Saturday, October 3, 4:00-5:00pm

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.

Speaker Bio

Mark Braverman is a postdoctoral researcher at the Microsoft Research New England lab in Cambridge, MA. He received his PhD from the University of Toronto in 2008. His research interests include computational and communication complexity, computability over the reals, and mechanism design.

< Schedule < EaGL-II homepage