Seminar: October 30, 2008, 3:45 (Ryerson 358)

Gil Kalai, Hebrew University and Yale University

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

Note non-standard day and room!

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: