Speaker:
David Gamarnik
Title:
On the uniqueness of Lebesgue measure on regular trees and the problem of computing the volume of a polytope.
Abstract:
The algorithmic problem of computing the volume of a convex body is known to admit a polynomial time approximation scheme.
A special class of this problem is the problem of computing the volume of a polytope. One can think of the volume of a polytope
as the partition function corresponding to the (continuous) counting Gibbs measure associated with hard (linear) constraints.
It is now known that for certain counting problems, the onset
of hardness for designing approximation algorithms coincides with the existence of a phase transition.
Motivated by this link, we study the phase transition property associated
with the independent set polytope supported on a regular tree.
We prove that the model does not exhibit the phase transition property, regardless of the degree of the tree.
This result leads to the prospect of designing a deterministic approximation algorithm for computing the volume of a polytope.
Joint work with Kavita Ramanan.