Statistical mechanics and algorithms on sparse and random graphs

This page contains material relevant for the following tutorials

• Brazil School of Probability, 2008

• Symposium on the Theory of Computer Science (STOC), 2010

• Seminar on Stochastic Processes, Duke 2012

• St. Flour Lectures on Probability Theory and Statistics, 2013

Lecture notes:

1. A. Dembo and A. Montanari, Gibbs measures and phase transitions on sparse random graphs, Brazil 2008

2. A. Montanari, Statistical mechanics and algorithms on sparse and random graphs, St. Flour 2012
   (This is a very incomplete and rough DRAFT. Will be updated regularly.)

Slides/handwritten notes:

1. Background on hidden clique

Some useful papers (an incomplete list, to be updated):

1. D. Aldous and R. Lyons, Processes on Unimodular Random Networks

2. A. Dembo and A. Montanari, Ising models on locally tree-like graphs

3. A. Montanari, E. Mossel, A. Sly, The weak limit of Ising models on locally tree-like graphs

4. A. Dembo, A. Montanari and N. Sun, Factor models on locally tree-like graphs

5. M. Bayati, D. Gamarnik, P. Tetali, Combinatorial approach to the interpolation method and scaling limits in sparse random graphs

6. A. Dembo, A. Montanari, A. Sly, N. Sun, The replica symmetric solution for Potts models on d-regular graphs

7. A. Sly, N. Sun, The computational hardness of counting in two-spin models on d-regular graphs

8. A. Montanari, Graphical Models Concepts in Compressed Sensing

9. M. Bayati, M. Lelarge and A. Montanari, Universality in Polytope Phase Transitions and Message Passing Algorithms

10. Y. Deshpande and A. Montanari, Finding Hidden Cliques of Size in Nearly Linear Time