DIMACS Princeton Theory Seminar


Title:

Sampling lattice points of polytopes

Speaker:

Santosh Vempala
CMU and Yale

Place:

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

Time:

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

Contact:

Sanjeev Arora (arora@cs.princeton.edu)

Abstract:

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