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.