Thrifty approximations of convex bodies by polytopes

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