Lab Home | Phone | Search
Center for Nonlinear Studies  Center for Nonlinear Studies
 Colloquia Archive 
 Postdoc Seminars Archive 
 Quantum Lunch 
 CMS Colloquia 
 Q-Mat Seminars 
 Q-Mat Seminars Archive 
 Kac Lectures 
 Dist. Quant. Lecture 
 Ulam Scholar 
 Summer Research 
 Student Application 
 Past Visitors 
 PD Travel Request 
 History of CNLS 
 Maps, Directions 
 CNLS Office 
Monday, March 05, 2012
3:00 PM - 4:00 PM
CNLS Conference Room (TA-3, Bldg 1690)


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,, 665-8119