Theoretical
models of
disordered
materials are
the prototypes
of
many challenging
mathematical
problems, with
applications
ranging from
theoretical
computer science
(random
combinatorial
problems) to
communications (detection,
decoding,
estimation).
This course
treats the
underlying
structure common
to
many such
problems, namely
large systems of
discrete
variables that
are strongly
interacting
according
to a mean field
model determined
by a random
sparse graph.
Plan of the
course:
1. Introduction:
Models on graphs,
Phase
transitions,
Gibbs measures,
Mean field
equations,
Approximation by
trees.
2. Ferromagnetic
Ising model and
spin glass on
sparse graphs:
Convergence to
the tree measure,
Limiting free
energy.
3. The general
case: Bethe
measures,
extremality.
Belief
propagation
algorithm and
the Cavity
method.
4.
Reconstruction
on trees and
random graphs.
Constraint
satisfaction
problems,
Clustering phase
transition.
5. Finite-size
scaling, the ODE
method and its
refinement
through
diffusion limit
and strong
approximation.
Application to
coding theory.