Combinatorics Seminar

When: Sunday, January 18, 10am Where: Schreiber 309 Speaker: Gil Kalai, Hebrew University 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 (1998). 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 stablest" theorem (Mossel, O'Donnell, Oleszkiewicz 05 http://front.math.ucdavis.edu/0503.5503) and the connection to hardness of approximation.