Thrifty approximations of convex bodies by polytopes

School of Mathematics Colloquium
Thursday, March 7, 2013 - 11:00
1 hour (actually 50 minutes)
Skiles 006
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.