Los Alamos National Laboratory

Science >  LANL Institutes

National Security Education Center


ISTC Seminar: Statistical Physics and Algorithms for Graph Counting Problems

March 4, 2009
Time: 3:00 pm
Location: CNLS Conf Rm

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.



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.

<< Back to calendar
Operated by Los Alamos National Security, LLC for the U.S. Department of Energy's NNSA
Inside | © Copyright 2008-09 Los Alamos National Security, LLC All rights reserved | Disclaimer/Privacy | Web Contact