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
READING PERIODS:
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
read about it.]
- 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]
- 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
[2]
- 8. Friedgut's theorem that low influence functions can
be approximated by juntas [7]
- 9. Influence results for nonsymmetric coins [8]
- 10. Application of the influence results to the sharp threshold
theorem
of Friedgut and Kalai for transitive events. [9]
- 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) [12]
- 14. Noise sensitivity of percolation (Benjamini, Kalai, Schramm)
[12]
- 15. Noise sensitivity and noise stability exponents
for general Boolean functions [13]
- 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) [16]
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 )