Random graphs, statistical physics and complexity

Statistical physics models for disordered materials provide precise predictions about the typical complexity of certain combinatorial optimization problems. The underlying common structure is that of many discrete variables, whose interaction is represented by a random sparse graph. 

I will discuss recent progress in proving some of these predictions. In particular, on the emerging theory of nonlinear large deviations, yielding mean field approximation for certain Gibbs measures and representing such measures as mixtures of not too many product measures.