Stats 316 Stochastic Processes on Graphs Spring 2010

Class Times and Locations Monday and Wednesday, 2:15PM-3:30PM in Room: Sequoia 200 Course Description We will study probabilistic models for large systems of discrete variables interacting according to general graphs. Local weak convergence, Gibbs measures on trees, cavity method and replica symmetry breaking. Examples include: random k-satisfiability, the assignment problem, spin glasses, neural networks. References We will use the following lecture notes. A. Dembo and A. Montanari, Gibbs Measures and Phase Transitions on Sparse Random Graphs. (based on course taught at the 2008 Brazilian School of Probability) Selected portions of the foollowing texts will be `visited' during the course. M. Mézard and A. Montanari, Information, Physics and Computation, Draft pdf files (plus Chapter 17 [pdf]) M. Talagrand, Spin Glasses: A Challenge for Mathematicians : Cavity and Mean Field Models R. Lyons with Y. Peres, Probability on Trees and Networks Prerequisites STAT310A or equivalent (STAT310B or equivalent is also recommended). What is the figure on the right ? It is a 3-coloring (green-blue-reed) of a 3-regular tree. This coloring has two peculiarities: (1) It is proper (no edge has both ends of the same color); (2) We leave to you the puzzle of finding the second peculiarity. [Courtesy of Peter Winkler]

• Amir Dembo
  • Office: Sequoia 129
  • Office hours: Thursdays 11:00AM-1:00PM
  • email: adembo@stat.stanford.edu

• Andrea Montanari
  • Office: Packard 272
  • Office hours: Tuesdays and Thursdays 2:30PM-4:00PM.
  • email: montanari@stanford.edu

This course is oriented towards research in applied probability with active participation by all the students attending it. Students are invited for form small groups (ideally 2 people) and get involved in a small research project. Project suggestions and relevant references will be provided below.