MIT Probability Seminar

Monday, September 27, 2021 at 4:00pm to 5:30pm

Building 2, 2-147
182 MEMORIAL DR, Cambridge, MA 02139

Speaker: Lisa Sauermann  (MIT)

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.

Event Type


Events By Interest


Events By Audience


Events By School

School of Science


prob_sem, aldixon


Department of Mathematics


Contact Email

Add to my calendar

Recent Activity

You're not going yet!

This event requires registration.