# 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