# 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:

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

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:

Background on hidden clique

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

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

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

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

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

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

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

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

A. Montanari, Graphical Models Concepts in Compressed Sensing

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

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