### Thrifty approximations of convex bodies by polytopes

- Series
- School of Mathematics Colloquium
- Time
- Thursday, March 7, 2013 - 11:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Alexander Barvinok – University of Michigan

Given a d-dimensional convex body C containing the origin in
its interior and a real t>1, we seek to construct a polytope P with
as few vertices as possible such that P is contained in C and C is
contained in tP. I plan to present a construction which breaks some
long-held records and is nearly optimal for a wide range of parameters d
and t. The construction uses the maximum volume ellipsoid, the John
decomposition of the identity and its recent sparsification by Batson,
Spielman and Srivastava, Chebyshev polynomials, and some tensor
algebra.