| 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.