MIT Probability Seminar
Monday, September 27, 2021 at 4:00pm to 5:30pm
Building 2, 2-147
182 MEMORIAL DR, Cambridge, MA 02139
Title: On the extension complexity of random polytopes.
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 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.