Seminar
| Parent Program: | |
|---|---|
| Location: | SLMath: Eisenbud Auditorium |
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.