MATH 290K: Spring 2012

Current Literature Seminar

CONCENTRATION OF MEASURE

MATH 290K: Spring 2012

(this is an initial website for a reading course on the Concentration of Measure Phenomenon)

Lectures

Date	Topic	Speakers	Notes
4/2	Basic concepts	Oren Louidor	All
4/9	Isoperimetry	Guy David and Anand Rajagopalan	Part 1
4/16	Poincaré and Log Sobolev	Rostyslav Kozhan and Thomas Leblé	Part 1, Part 2
4/23	Martingales	Tilman Wolff and William Rosenbaum	Part 2
5/7	Talagrand's inequality	Nicholad Cook	All
5/14	Transportation Cost	Fuxi Zhang and Benjamin Hayes
5/21	Influences	Oren Louidor
5/28	Emperical and Gaussian Processes	Dan Ben-Moshe and Anand Rajagopalan
6/4	Applications	Thomas Alberts and Alexander Vandenberg-Rodes

Times & Place: Monday 3:00-5:50, MS 5118 (tentative). See the posting on the Registrar.

Organizers: Marek Biskup, Oren Louidor.

Description: "Concentration of measure" is a phenomenon where a measure (usually defined on a space of large but finite dimension) has most of its support concentrated on a set of very small diameter. An alternative formulation states that smooth functions on this measure-space typically attain a very small range of values. This phenomenon is of interest both by itself (from the point of view of geometric functional analysis) and through applications in many models of probabilistic and geometric nature.

The aim of the course is two-fold:

Introduce the participants to the general theory of concentration of measure as has been developed in the past 50 years by Milman, Gromov, Schechtman, Talagrand, Ledoux and others.
Show how the principles of the theory can be applied to concrete problems in analysis, combinatorics, theoretical computer-science, physics and probability.

Topics to be discussed (tentative and not exhaustive):

Formal definition. Geometrical and probabilistic point of view. Levy families.
Martingale methods - Chernoff, Azuma, Hoeffding, Bernstein.
Isoperimetric inequalities.
Entropy and Log-Sobolev inequalities.
Transportation cost inequalities.
Talagrand's inequalities.
Concentration in product spaces.
Concentration for Gaussian processes.
Concentration for empirical processes.
If time permits:
- Discrete Fourier analysis and influence.
Examples in: Euclidean space, spin-glasses, random matrices, random graphs, stochastic optimization, branching processes, graph coloring, increasing subsequences, harmonic measures, permutations, etc

Logistics: Closer to the beginning of the quarter, we will generate a course schedule which will outline precisely the topic to be discussed in each week of the quarter. Each lecture will be assigned to a participant, which will be responsible for presenting the material as well as typing notes. We expect to have enough participants to allow for a maximum of one lecture preparation per participant. Notes from all lectures will be collected to form a complete set, which will be available for download in the end of the course.

Books:

Asymptotic Theory of Finite Dimensional Normed Spaces by V. Millman, G. Schetman. Online via SpringerLink .

The Concentration of Measure Phenomenon by M. Ledoux. Introduction and TOC, if desperate look here
Concentration of Measure For the Analysis of Randomised Algorithms by D. Dubhashi, A. Panconesi. Old draft online.

Lecture Notes:

By N. Berestycki and R.Nickl (University of Cambridge).
By Gabor Lugosi (Pompeu Fabra University - Spain).