Logo

Mathematical Sciences Research Institute

Home » GFA Young Researchers Seminar: John's position is not good for approximation

Seminar

GFA Young Researchers Seminar: John's position is not good for approximation October 18, 2017 (11:15 AM PDT - 12:30 PM PDT)
Parent Program:
Location: MSRI: Simons Auditorium
Speaker(s) Han Huang (University of Michigan)
Description No Description
Video
No Video Uploaded
Abstract/Media

Consider an n-dimensional convex body K in John's position. For R>1, we want to approximate K with geometric distance R by a polytope P with few facets.

In the symmetric case, one can construct P using contact points of K with square in n facets to provide a good approximation for R equal to the square root of n. It was generalized later by Barvinok for R of different orders.

In this talk, we'll show that in the non-symmetric case John's position is not good for approximation:

1. If R is square root of n, there exists K in John's position such that any polytope P approximating K with geometric distance R has at least exponential in n number of facets.

2. If R is of order o(n), there exists K in John's position such that any polytope P approximating K with geometric distance R has at least super-polynomial in n number of facets.

No Notes/Supplements Uploaded No Video Files Uploaded