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.

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

Homework 1 Due October 30.

Homework 2 Due November 23.

Homework 3 Due February 1.

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.

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.

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.

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

mathematics and mathematical statistics. Faculty are also of course welcome.

probability and analysis. Mathematical maturity of course is good.

Feel free to talk to me if you are unsure.

examination at the end. Students might be asked to present a

specific topic (but this is not yet decided).

email: steif"at"chalmers.se

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 )