Lab Home | Phone | Search
	Center for Nonlinear Studies
	Home  ▶ People   Current   Executive Committee   Postdocs   Visitors   Students   Research   Publications  ▶ Conferences   Workshops   Sponsorship  ▶ Talks   Seminars   Postdoc Seminars Archive   Quantum Lunch   Quantum Lunch Archive   P/T Colloquia   Archive   Ulam Scholar     Postdoc Nominations  ▶ Student Requests   Student Program  ▶ Visitor Requests   Description   Past Visitors  ▶ Services   General     History of CNLS     Maps, Directions   CNLS Office   T-Division   LANL				Wednesday, March 04, 20093:00 PM - 4:00 PMCNLS Conference Room (TA-3, Bldg 1690) Seminar Statistical Physics and Algorithms for Graph Counting Problems David GamarnikOperations Research, MIT Sloan School of Management 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. Host: Misha Chertkov, T-4