Statistical Physics, Interpolation Method and Scaling Limits in Sparse Random Graphs

Date

March 2, 2011

Overview

Statistical physics, provided powerful insights into the theory of combinatorial structures and algorithms. For example, the success of certain counting algorithms is well known to be linked with the phase transition properties of the underlying combinatorial model.

Recently, however, a new powerful method was developed in the statistical physics of spin glasses, based on the interpolation idea. Among other things, the interpolation method was used to prove the existence of the so-called free energy thermodynamic limits for several spin glass models. In this talk we will discuss applications of the interpolation method in the context of combinatorial optimization problems on sparse random graphs. Using this method we establish the existence of scaling limits for a variety of combinatorial problems, including Maximum Independent Set, MAX-CUT, Coloring, K-SAT, and related problems. For these models, we show that the optimal values, appropriately normalized, converge to a limit with high probability, as the size of the underlying graph diverges to infinity. For the case of Independent Set model, this resolves a problem which was proposed by David Aldous in 2000 as one of his six favorite open problems. The talk will be completely self-contained. No background on the theory of random graphs or statistical physics is necessary.

Joint work with Mohsen Bayati (Stanford) and Prasad Tetali (Georgia Tech).

Speakers

David D. Gamarnik

David Gamarnik is an associate professor of operations research at the Sloan School of Management of Massachusetts Institute of Technology.
He received B.A. in mathematics from New York University in 1993 and Ph.D. in Operations Research from MIT in 1998. Since then he worked in the Department of Mathematical Sciences, IBM Research, before joining MIT in 2005.
His research interests include applied probability and stochastic processes, theory of random graphs and algorithms, combinatorial optimization, statistical learning theory and various applications. He is a recipient of the Erlang Prize from the INFORMS Applied Probability Society, IBM Faculty Partnership Award and several NSF sponsored grants.
He serves as an associate editor of the Annals of Applied Probability, Operations Research, Mathematics of Operations Reserach and Queueing Systems journals.

‚Äč