Random graphs, statistical physics and complexity

Speaker
Amir Dembo (Stanford)
Date
11/02/2024 - 13:00 - 12:00Add to Calendar 2024-02-11 12:00:00 2024-02-11 13:00:00 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. Hybrid mode: math building (216), room 201, and zoom: https://biu-ac-il.zoom.us/j/751076379 אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Hybrid mode: math building (216), room 201, and zoom: https://biu-ac-il.zoom.us/j/751076379
Abstract

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.

Last Updated Date : 06/02/2024