Stat 206A: Polynomials of Random Variables, Fall 2005

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, 5-6:30pm, Evans 1011.

 

Instructor: Elchanan Mossel (mossel@stat dot berkeley dot edu)

 

Grade: The grade will be based on the following:

  1. Participation.
  2. Scribing two lectures. You can find a latex file here.
  3. Submitting two homework problems.
  4. Presenting a paper at the end of the term.

Scribe Notes:
Aug 30, Informal Overview and Motivating Examples : ps / pdf                             Sep 1, L2 and Tensors      : ps / pdf  
Sep 6, General Chaos Decomposition, Hermite Expansion   : ps / pdf                      Sep 8, Hermite Polynomials and Fourier expansion of Symmetric Functions, Influence : ps / pdf                  
Sep 13, Discrete Isoperemetric Inequalities (Harper) : ps / pdf                                  Sep 15, Influences and Query Complexity (Schramm et. al.)    : ps / pdf
Sep 20, Continued ps / pdf                                                                                        Sep 22, PAC learning under uniform distribution : ps / pdf
Sep 27 :Learning monotone functions, functions of a few variables ps / pdf             Sep 29, Learning functions of a few variables, continued:  ps / pdf
Oct 4, Noise Operators   : ps / pdf                                                                              Oct  6, Bonami-Beckner Hyper-Contraction: ps / pdf   (A different set of scribe notes for Oct 4   : ps / pdf )
Oct 11, General Hyper-Contractivity: ps / pdf                                                            Oct 13: Guest lecture: Prof. D. Aldous
Oct 18: Hyper-Contraction and Invariance ps / pdf                                                    Oct 20: Invariance Continued ps / pdf
 and slides: ppt html
Oct 25: KKL + Talagrand ps / pdf                                                                             Oct 27: Low Influence functions, Threshold for monotone functions ps / pdf
Nov 1 : Coin Tossing Protocols: ppt / pdf
A guest lecture by Ryan O'Donnell on Grothendieck Inequality, Nov 22: ps / pdf

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, Cambridge, UK, 1997. ISBN: 0-521-56128-0.

. M. Ledoux:  Isoperimetry and Gaussian analysis ( ps , pdf ).

. Daniel Stefankovic. Fourier transforms in computer science. Master's Thesis, University of Chicago, Department of Computer Science, TR-2002-03.

. 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

 

 Suggestions for final projects: (assigned projects were already chosen by students in the class; You must choose a project by Oct 25)

. Wick Product and Wick exponentials (Janson Chapter 3) -- assigned..

. Variables with finite Chaos decomposition (Janson Chapter 6) -- assigned. 

. Random Potential in networks (Janson Chapter 9) - assigned. 

. Hyper-contractivity and the log Sobolov constant (Bakry St. Flour lecture notes is a good source)

. Talagrand concentration inequality (a good reference is the "Probabilistic method" by Alon and Spencer)

. The Fourier spectrum of monotone function (Talagrand's : How Much +  Mossel,O'Donnell: on the noise sensitivity on monotone functions). 

. Limit theorem for U statistics (Dynkin and Mandelbaum 1983 and Janson chapter 11)

. Noise Stability and Majority functions (Benjamini, Kalai, Schramm) 

. Influences and threshold under group symmetries (Bourgain, Kalai)

. Guassian isoperemetric problems (Borell 85, Ledoux lecture notes, chpater 8)

. Stability of weighted majority functions (Noise stability of weighted majority by Peres)

. Noise sensitivity and exceptional times for percolation (Steif + Schramm) -- assigned.

. Functions that can be evalauted where every input is unlikely to be read (Benjamini, Schramm, Wilson) -- assigned. 

. Bounds on \eps biased generators (Mossel+Shpilka+Trevisan)

. Gowers uniformity and PCP (Samorodnitsky +  Trevisan).

. A Katona-type proof of an Erdos-Ko-Rado-type (Friedgut) -- assigned.

. Probabilistic view of Arrow's theorem (Kalai 2002) -- assigned. 

. Probabilistic view of MacGarvey theorem (Kalai 2004) -- assigned. 

. Influences for non-product spaces (Haggstrom+Kalai+Mossel; Graham+Grimmett) -- assigned

. Learning from Random Walks (Bshouty, Mossel, O'donnell, Servedio) -- assigned.

 . The Fourier tails of AC0 circuits (Linial, Mansour and Nisan 93 or Stefnakovitc thesis)

. Khot unique games -- assigned. 

. Hardness of MAX-CUT -- assigned (Khot, Kindler, Khot,Mossel) -- assigned.

. Indpendent sets in coloring and their hardness (Dinur, Mossel, Regev)

. Fourier methods in embedding theory (Khot-Vishnoy) -- assigned.

. Fourier methods and the edit distance (Khot-Naor, Krauthgamer-Rabani) -- assigned. 


Department of Statistics

Elchanan Mossel's homepage