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.]

    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 )