# Noise sensitivity, sharp thresholds and influences (fall, 2009)

PLACE: MV L15

Class times information for coming 2 weeks.

Weeks 3 and 4, Monday 13:15-15:00 and Friday 10:15-12:00

This course will start at the beginning of October and go through
the second reading period and perhaps somewhat into the third.

POINTS:
7 1/2 "new style" points (5 "old style" points)

Homeworks:
Homework 1 Due October 30.

Homework 2 Due November 23.

Homework 3 Due February 1.

• WHAT IS THE SUBJECT OF THE COURSE?

• Noise sensitivity and noise stability

Many systems are described by some complicated function of many
underlying i.i.d. random variables. Certain of these systems are
'noise sensitive' in the sense that a small perturbation (noise) of the
underlying variables can greatly affect the outcome of the full system.
Other systems are 'noise stable' in the sense that the global system is
not greatly affected by such noise.

The mathematics behind these questions is first Fourier analysis on a
discrete high dimensional cube (i.e., (Z/2)^n) and the above questions
are related to where the spectra of the function describing the global
system has most of its weight. The second mathematical tool which
comes into play is the notion of hypercontractivity from analysis.

• Sharp thresholds

In many systems, the probability of some global event (which depends on
many underlying i.i.d. random variables) undergoes a sharp threshold as
the parameter of the underlying variables is varied. Often the probability
goes from very small to very large as the parameter for the underlying
variables varies very little.

• Influences

The notion of influence is the degree to which a global system depends
on a particular variable. This notion is central to the two first topics above.

• WHAT WILL WE TRY TO COVER?
[The following is an outline which might change with time (it's probably too much material) . The numbers
after each topic refer to the references below in terms of where one can
• 1. Overview of noise sensitivity, sharp thresholds and influences.
• 2. Definition of influences. [2,3,4,13]
• 3. Basic Fourier analysis on (Z/2)^n [1,2,3]
• 4. Relationship between influences and spectral behavior [3,4,13]
• 5. Hypercontractivity and the Gross-Bonami-Beckner inequality 
• 6. The celebrated result by Kahn, Kalai and Linial (KKL) on the log n/n
lower bound for the maximum influence [3,4]
• 7. The KKL result of sets of size n/log n whose influence is near 1 
• 8. Friedgut's theorem that low influence functions can be approximated by juntas 
• 9. Influence results for nonsymmetric coins 
• 10. Application of the influence results to the sharp threshold theorem
of Friedgut and Kalai for transitive events. 
• 11. Application of influence/sharp threshold results to determining the
critical value of 2-d percolation (Kesten, Russo, Bollobas, Riordan) [10,11]
• 12. Description of noise sensitivity and noise stability in terms of
spectral behavior (Benjamini, Kalai, Schramm) [12,13]
• 13. The L_2 norm of the influence vector going to 0 implying noise
sensitivity (Benjamini, Kalai, Schramm) 
• 14. Noise sensitivity of percolation (Benjamini, Kalai, Schramm) 
• 15. Noise sensitivity and noise stability exponents for general Boolean functions 
• 16. Overview of results on these exponents for percolation using random algorithims (Schramm, Steif) [13,14]
• 17. Overview of results on these exponent for percolation using the geometry of the spectral distribution (Garban, Pete, Schramm) [13,15]
• 18. Some applications to random complexity lower bounds in theoretical
computer science (O'Donnell, Saks, Schramm, Servedio) 

INTENDED AUDIENCE: This course is intended for graduate students in
mathematics and mathematical statistics. Faculty are also of course welcome.

PREREQUISITES: One should have been exposed to graduate level
probability and analysis. Mathematical maturity of course is good.
Feel free to talk to me if you are unsure.

EXAMINATION: There will be home-assignments, and an oral
examination at the end. Students might be asked to present a
specific topic (but this is not yet decided).

EXAMINATOR: Jeff Steif
email: steif"at"chalmers.se

COURSE LITERATURE : There will be no official book since there is
no book covering this material. Material will be based on the lectures.
However the following references will contain much of what we will do.
(I can provide these for you but won't put them here for fear of breaking copyright law).

1. (second section of Lecture 2) here

2. Fourier transform on the hypercube. J. Sjostrand.

3. Kahn, J., Kalai, G. and Linial, N. The influence of variables on boolean functions. {\em 29th Annual Symposium on Foundations of Computer Science}, (1988), 68-80.

4. (notes number 13) here

5. (Some parts of 4.5 and 4.6) here

6. (notes number 12) here

7. Friedgut, Ehud Boolean functions with low average sensitivity depend on few coordinates. Combinatorica 18 (1998), no. 1, 27--35

8. Influences of Boolean Functions under a Biased Measure by Marcus Isaksson here

9. Friedgut, Ehud; Kalai, Gil Every monotone graph property has a sharp threshold. Proc. Amer. Math. Soc. 124 (1996), no. 10, 2993--3002.

10. Bollob\'as B. and Riordan O.M. A short proof of the Harris Kesten Theorem, Bull. London Math. Soc., 38}, (2006), 470-484. here

11. A note on the Harris-Kesten Theorem. Bela Bollobas, Oliver Riordan. Europ. J. Combin. 28 (2007), 1720-1723. here

12. Benjamini, Itai; Kalai, Gil; Schramm, Oded Noise sensitivity of Boolean functions and applications to percolation. Inst. Hautes Etudes Sci. Publ. Math. No. 90 (1999), 5--43 (2001)

13. A survey on dynamical percolation. Jeffrey E. Steif. (Section 4). here

14. Quantitative noise sensitivity and exceptional times for percolation. Oded Schramm, Jeffrey E. Steif. here

15. The Fourier Spectrum of Critical Percolation by Christophe Garban, Gabor Pete, Oded Schramm here

16. Every decision tree has an influential variable by R. O'Donnell, M. Saks, O. Schramm, R. Servedio. (to be found at here )