Computer Science/Discrete Mathematics Seminar II
Poly-logarithmic Independence Fools ACO Circuits
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.
Date & Time
February 03, 2009 | 10:30am – 12:30pm
Location
S-101Speakers
Affiliation
Microsoft Research New England