DIMACS Theoretical Computer Science Seminar

Title: Poly-logarithmic independence fools AC0 circuits

Speaker: Mark Braverman, Micorsoft Research

Date: Wednesday, February 4, 2009 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


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.