Springe direkt zu Inhalt

Lecture by Lisa Sauermann (Institute for Advanced Study, Princeton): On the extension complexity of low-dimensional polytopes

Nov 16, 2020 | 02:15 PM

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


Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)