 |
Center for Nonlinear Studies |
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