DIMACS Princeton Theory Seminar


Sampling lattice points of polytopes


Santosh Vempala
CMU and Yale


Room 402, Computer Science Building
35 Olden Street
Princeton University.


12:05 PM (Lunch will be served at 11:45 AM)
Friday, February 21, 1997


Sanjeev Arora (arora@cs.princeton.edu)


Ravi Kannan and Santosh Vempala

When is the volume of a convex polytope in $\reals^n$ close to the number of lattice points in the polytope? We show that if the polytope contains a ball of radius $n\sqrt{\log k}$, where $k$ is the number of facets, then the volume approximates the number of lattice points to within a constant factor. This general condition is then specialized to derive polynomial time sampling and counting algorithms for various combinatorial problems whose solutions can be viewed as lattice points of convex polytopes. We also show, via tight examples, that our condition is essentially the best possible.

Document last modified on February 11, 1997