Group:Algorithms, Complexity and Cryptography Group
Title: On the entropy-influence conjecture and spectral width
Speaker: Andrew Wan University
Time: 2011-11-11 14:00-2011-11-11 15:30
Venue: FIT 1-222

Abstract:

I will introduce and discuss the entropy-influence conjecture (Friedgut-Kalai 96), related results such as the Kahn-Kalai-Linial theorem (see links below), Friedgut's theorem, and Bourgain's distributional inequality.

 

I will also discuss special cases and present recent work by O'donnell, Wright and Zhou, which proves the conjecture for symmetric functions.

 

Kahn-Kalai-Linial: http://portal.acm.org/citation.cfm?id=1398603
Friedgut: http://www.springerlink.com/index/FXCJ48RNBWV5GJDB.pdf
Bourgain: http://www.springerlink.com/index/657221R06X818652.pdf
O'donnell et al.: http://www.cs.cmu.edu/~odonnell/papers/fei.pdf
an>