# DIMACS Princeton Theory Seminar

## Title:

Sampling lattice points of polytopes

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.