This course will survey the foundations of the mathematical theory of polynomials of independent random variables. This theory involves discrete mathematics, analysis, high dimensional geometry, probability in Gaussian spaces and more. In the course we will intertwine the theory with applications from learning, concentration of measure, threshold phenomena, percolation, isoperimetric inequalities, social choice in economy and hardness of approximation in theoretical computer science.
Prerequisites: Strong
background in probability and analysis. Interest in some of the
application
fields (Statistics, Probability, high
dimensional phenomena,
Theoretical Computer Science or Economy).
One year of Stat 205
or Stat 204 is required. Students who have not taken Stat
205 or Stat
204 and students who feel they may not have sufficient mathematical
background
are encouraged to contact the instructor in order to verify that they
have the
appropriate background.
Lectures: Tuesday & Thursday,
Instructor: Elchanan Mossel
(mossel@stat dot
Grade: The grade will be based on the following:
Tentative plan:
1. Fourier representation on finite probability spaces. Chaos decomposition in Gaussian spaces.
2. Application: Fourier learning.
3. Hyper-Contraction in finite and Gaussian spaces.
4. Application: Concentration of measure.
5. Influences. Lower bounds on influences.
6. Application: Threshold Phenomena.
7. Noise sensitivity.
8. Application: percolation.
9. Gaussian and Spherical measures in high dimensions.
10. Application: isoperimetric inequalities.
11. Invariance principles.
12. Applications: Social choice.
13. Applications: Hardness of Approximation.
Bibliography:
. S. Janson: Gaussian Hilbert Spaces. Cambridge
University Press,
. M. Ledoux: Isoperimetry and Gaussian analysis ( ps , pdf ).
. Daniel Stefankovic.
Fourier transforms in computer science.
Master's Thesis,
. van Zwet, W. R. A Berry-Esseen
bound for symmetric statistics.
Z. Wahrsch. Verw. Gebiete 66 (1984), no. 3, 425--440.
. Elchanan Mossel, Ryan ODonnell,
Rocco Servedio: Learning Juntas, STOC 2003.
. G. Kalai, N. Linial and J. Kahn: The influence of variables on Boolean functions, FOCS 1988, 60-88.
. M. Talagrand: How much are increasing sets correlated?,Combinatorica 16, 1996, 243-258.
. M. Talagrand: On boundaries and influences, Combinatorica 17, 1997, 275-285.
. E.
Friedgut & Gil Kalai:
Every
Monotone Graph Property Has a Sharp Threshold.
Proc. Amer. Math. Soc. 124 (1996), pp. 2993-3002.
. E. Friedgut: Boolean Functions with Low Average Sensitivity Depend on Few coordinates. Combinatorica Vol 18 (1) 1998 pp. 27-36..
. E. Friedgut: Sharp Thresholds of Graph Proprties,
and the $k$-sat Problem. J. Amer. Math. Soc. 12 (1999), no. 4, 1017—1054. Appendix by J. Bourgain.
. I. Benjamini, G. Kalai and O. Schramm: Noise Sensitivity of Boolean Functions And Applications to Percolation, Publ. I.H.E.S. 90 (1999), 5-43.
. I. Benjamini, G. Kalai and O. Schramm: Improved variance bounds for first passage percolation, , Ann. Probab. 31 (2003), no. 4, 1970--1978.
. G. Kalai: A Fourier-Theoretic Perspective for the Condorcet Paradox and Arrow's theorem, Adv. in Appl. Math. 29(2002), 412-426
. G. Kalai: Social Indeterminacy, Econometrica, 72 (2004), 1565-1581.
. S. Khot: On the power of unique 2-prover 1-round games.
(STOC/Complexity joint session, 2002)
. Elchanan Mossel,
Ryan O'Donnell, Krzysztof Oleszkiewicz:
Noise
stability of functions with low influences: invariance and optimality
. Irit Dinur, Elchanan Mossel, Oded Regev: Conditional Hardness for Approximate Coloring
. The Fourier tails of AC0 circuits (Linial, Mansour and Nisan 93 or Stefnakovitc thesis)