Computer Science/Discrete Mathematics Seminar II

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, I will first give some background on extension complexity and explain its connection to the notion of non-negative rank. I will then discuss some results on the extension complexity of random polytopes (which are obtained as the convex hull of independent random points either in the unit ball or on the unit sphere), which are joint work with Matthew Kwan and Yufei Zhao. Our results prove that the extension complexity of these random polytopes is typically on the order of the square root of number of vertices of the polytope.