Lab Home | Phone | Search
Center for Nonlinear Studies  Center for Nonlinear Studies
 Home 
 People 
 Current 
 Affiliates 
 Visitors 
 Students 
 Research 
 ICAM-LANL 
 Publications 
 Conferences 
 Workshops 
 Sponsorship 
 Talks 
 Colloquia 
 Colloquia Archive 
 Seminars 
 Postdoc Seminars Archive 
 Quantum Lunch 
 Quantum Lunch Archive 
 CMS Colloquia 
 Q-Mat Seminars 
 Q-Mat Seminars Archive 
 P/T Colloquia 
 Archive 
 Kac Lectures 
 Kac Fellows 
 Dist. Quant. Lecture 
 Ulam Scholar 
 Colloquia 
 
 Jobs 
 Postdocs 
 CNLS Fellowship Application 
 Students 
 Student Program 
 Visitors 
 Description 
 Past Visitors 
 Services 
 General 
 
 History of CNLS 
 
 Maps, Directions 
 CNLS Office 
 T-Division 
 LANL 
 
Monday, March 05, 2012
3:00 PM - 4:00 PM
CNLS Conference Room (TA-3, Bldg 1690)

Colloquium

On the uniqueness of Lebesgue measure on regular trees and the problem of computing the volume of a polytope.

David Gamarnik
Massachusetts Institute of Technology

The algorithmic problem of computing the volume of a convex body is known to admit an efficient (polynomial time) approximation scheme. A special class of this problem is the problem of computing the volume of a polytope - the set determined by intersections of hyperplaces. Polytopes can be represented as graphical model with factor nodes corresponding to validity of linear constraints. Recently it was shown that for certain graphical model the onset of hardness of designing approximation algorithms for inference coincides with the existence of a certain phase transition property, thus establishing a very intriguing connection between the complexity theory of algorithms and statistical physics. Motivated by this link we study the phase transition property associated with the graphical model corresponding to the polytope representation. Focusing on the special case of polytopes supported on tree-like graphical models, we show that the model never exhibits the phase transition property, consistently with the existence of an efficient algorithm. This result leads to a prospect of a new type of algorithms for the volume computation problem, not relying on randomization. Joint work with Kavita Ramanan.

Host: Misha Chertkov, chertkov@lanl.gov, 665-8119