Lecture by Lisa Sauermann (Institute for Advanced Study, Princeton): On the extension complexity of low-dimensional polytopes
It is sometimes possible to represent a complicated polytope as a projection of a much simpler polytope. To quantify this phenomenon, the extension complexity of a polytope P is defined to be the minimum number of facets in a (possibly higher-dimensional) polytope from which P can be obtained as a (linear) projection. In this talk, we discuss some results on the extension complexity of random d-dimensional polytopes (obtained as convex hulls of random points on either on the unit sphere or in the unit ball), and on the extension complexity of polygons with all vertices on a common circle.
Joint work with Matthew Kwan and Yufei Zhao.
Time & Location
Nov 16, 2020 | 02:15 PM