ISTC Seminar: Statistical Physics and Algorithms for Graph Counting Problems

IS&T Center Seminar Series

March 4, 2009

Wednesday, 3 PM, CNLS Conference Room (TA-3, SM-1690, Rm. 102)

Speaker: Professor David Gamarnik, Operations Research, MIT Sloan School of Management

Host:  Misha (Michael) Chertkov, Physics of Condensed Matter & Complex Systems (T-4)

Title:  Statistical Physics and Algorithms for Graph Counting Problems

Contact Misha Chertkov, chertkov@lanl.gov,  5-8119, if you wish to meet with David during his visit.

Abstract:

The talk will be devoted to recent developments connecting statistical physics and
theory of algorithms. We will illustrate this connection using graph countingproblems,
for example the problem of counting matchings.  Unlike prior algorithms which are
based on the Markov chain Monte-Carlo sampling method the new approach leads
to algorithms which are deterministic and thus do not require randomization.  The new
approach builds on the notion of correlation decay in statistical physics in connection with
the uniqueness property of Gibbs measures. We will then discuss applications of this
method to the problem of computing partition functions for lattice models.