[Colloquium] Talk by Mark Braverman on April 6, 2009

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Monday, April 6, 2009
Time: 3:45 p.m.
Place: RY 251

----------------------------------------------------------

Speaker:	Mark Braverman

From:		University of Toronto

Website: 	http://www.cs.toronto.edu/~mbraverm/

Title:      Poly-logarthmic Independence Fools AC0 Circuits

Abstract:      We will describe the recent proof of the 1990 Linial- 
Lisan 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.


Refreshments will be served prior to the talk in RY 255.