# 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