Asymptotic Analysis Seminar: Approximation Complexity of Convex Bodies

Tuesday, March 10, 2015 - 11:00am - 12:00pm
Lind 305
Mark Rudelson (University of Michigan)
Consider the approximation of an n-dimensional convex body by a projection of a section of an N-dimensional simplex, and call the minimal N for which such approximation exists the approximation complexity of the body. The reason for such strange definition lies in computer science. A projection of a section of a simplex is the feasible set of a linear programming problem, and so it can be efficiently generated. We will discuss how large the approximation complexity of different classes of convex bodies can be.