Poly-logarithmic Independence Fools ACO Circuits

COMPUTER SCIENCE/DISCRETE MATH II
Topic:Poly-logarithmic Independence Fools ACO Circuits
Speaker:Mark Braverman
Affiliation:Microsoft Research New England
Date:Tuesday, February 3
Time/Room:10:30am - 12:30pm/S-101

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.