[Colloquium] ROOM CHANGE: Talk by Gil Kalai, Thursday, October 30, 2008

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Thursday, October 30, 2008
Time: 3:45 p.m.
Place: RY 358

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

Speaker:	Gil Kalai

From:		Hebrew University and Yale University

Web page:	http://www.ma.huji.ac.il/~kalai/

Title:  Noise Sensitivity, Noise Stability, Percolation and some  
connections to TCS

Abstract: Noise sensitivity was defined in a paper by Benjamini,  
Kalai, and Schramm (1999). A closely related notion was considered by  
Tsirelson and Vershik. I will describe the notion of noise sensitivity  
of Boolean functions and some basic results and problems related to  
it. A fun way to explain it (especially after 2000) is in terms of the  
probability that small mistakes in counting the votes in an election  
will change the outcome. We will consider the following:
1. The definition of noise sensitivity, and how it is described in  
terms of the Fourier transform.

2. Noise sensitivity of the crossing event in Percolation (BKS 99,  
Schramm and Steiff 2005, and finally Garban, Pete, Schramm 2008 - http://front.math.ucdavis.edu/0803.3750 
  ), the scaling limit for the Spectral distribution (Schramm and  
Smirnov, 2007, GPS 2008), and dynamic percolation. (ScSt (2005), GPS  
(2008)). Other cases of noise sensitivity.

3. Noise stability of the majority function, of weighted majority. A  
conjecture regarding the situation for functions described by monotone  
depth monotone threshold circuits.

4. The "majority is stabelest theorem" (Mossel, O'Donnell,  
Oleszkiewicz 05 http://front.math.ucdavis.edu/0503.5503) and the  
connection to hardness of approximation.



There will be a reception in RY 255 before the talk.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20081027/7fca3080/attachment.htm