EVENT DETAILS AND ABSTRACT

Title: On the extension complexity of random polytopes
Speaker: Lisa Sauermann
Speaker Info: Stanford University
Brief Description:
Special Note:
Abstract:

Sometimes, it is 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 polytopes. For a fixed dimension d, we consider random d-dimensional polytopes obtained as the convex hull of independent random points either in the unit ball or on the unit sphere. In both cases, we prove that the extension complexity is typically on the order of the square root of number of vertices of the polytope. Joint work with Matthew Kwan and Yufei Zhao.