Stats 316 Stochastic Processes on Graphs Fall 2007–2008

Class Times and Locations Monday and Wednesday, 11:00AM-12:15PM 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 Selected portions of the foollowing texts will be `visited' during the course. In addition we will use handouts and papers. M. Mézard and A. Montanari, Book in preparation 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. 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: Wednesdays 2:30-4:15PM
  • email: adembo@stat.stanford.edu

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

Registered students are invited to form small groups of 2-4 peoples, and study one or more papers in the list below (together with references or further developments if useful). Each of the students will then present a short lecture (20 minutes) based on this material. Lectures by students in the same group should form a coherent sequence.

• M. Aizenman, J. Barsky and R. Fernandez, The Phase Transition in a General Class of Ising-Type Models is Sharp J. Stat. Phys. 47 (1987), 343
• D. Aldous, Asymptotics in the random assignment problem Prob. Theor. Rel. Fields, 93 (1992) 507-534
• E. Mossel and Y. Peres, Information flow on trees Ann. Appl. Probab. 13, (2003), 817-844. [TAKEN]
• A. Gerschenfeld and A. Montanari Reconstruction for models on random graphs FOCS 2007 [TAKEN]
• D. Achlioptas and C. Moore, The asymptotic order of the random k-SAT threshold FOCS 2002
• H. Daude, M. Mézard, T. Mora nad R. Zecchina, Pairs of SAT Assignment in Random Boolean Formulae Rand. Struct. Alg. (submitted)
• D. Weitz Counting independent sets up to the tree threshold STOC 2006
• D. Gamarnik and D. Katz Correlation decay and deterministic FPTAS for counting list-colorings of a graph
• D. Achlioptas and F. Ricci-Tersenghi On the solution-space geometry of random constraint satisfaction problems STOC 2006
• A. Dembo and A. Montanari Finite Size Scaling for the Core of Large Random Hypergraphs.

• M. Mézard and R. Zecchina Random K-satisfiability problem: From an analytic solution to an efficient algorithm Phys. Rev. E 66, 056126 (2002)
• F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, and L. Zdeborova Gibbs states and the set of solutions of random constraint satisfaction problems PNAS 104 (2007) 10318-10323