PROBABILISTIC ASPECTS OF COMBINATORIAL OPTIMIZATION AND DISORDERED
SYSTEMS
STAT 260, Fall 2001, David Aldous
MWF 3.00 -4.00, room 330 Evans.
The course will have three parts.
Some topics from J. Michael Steele's 1997 book
"Probability Theory and Combinatorial Optimization"
- Probabilistic analysis of classical Euclidean optimization problems
(Traveling Salesman, Minimum Spanning Tree, Mimimum Matching) using
subadditivity and the martingale concentration inequality.
- Weak convergence methodology.
- Talagrand's isoperimetric theory for proving concentration of measure.
Some topics from Michel Talagrand's 2000 lecture notes
"Mean Field Models for Spin Glasses: a First Course"
(To appear in:
Ecole d'ete de Probabilites de Saint-Flour, XXX -- 2000).
- The Random Energy Model
- The Sherrington-Kirkpatrick Model
- The p-spins model.
[These are well-studied in the physics literature; Talagrand brings a
mathematician's eye to the subject]
Recent papers on special problems
Contact me at: aldous@stat.berkeley.edu