Algorithmic Construction and Applications of M-Ellipsoids

Tuesday, September 27, 2011 - 2:00pm - 3:00pm
Keller 3-180
Santosh Vempala (Georgia Institute of Technology)
The M-ellipsoid of a convex body K is a fundamental object introduced by V. Milman. It has the same volume as K and can cover K with the union a small number of translations. There are several proofs of the existence of an M-ellipsoid. We present algorithms for constructing M-ellipsoids based on two of these proofs. The first is randomized and is via a proof by Klartag giving optimal covering bounds. The second, based on a proof by Pisier, achieves slightly weaker bounds but leads to a deterministic algorithm.

We use M-ellipsoids in a new algorithm for enumerating lattice points in a convex body. This has several consequences, including more efficient algorithms for (a) the shortest vector problem in any semi-norm (distance induced by a convex body) (b) integer programming (c) deterministic approximate volume computation.

This is joint work with Daniel Dadush and Chris Peikert.
MSC Code: