|Date: Friday, March 01, 2013
Location: 3866 East Hall (4:10 PM to 5:00 PM)
Title: Thrifty approximations of convex bodies by polytopes
Abstract: 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 vide 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.
Speaker: Alexander Barvinok
Institution: University of Michigan
Event Organizer: Sergey Fomin