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

Conferences/Seminars/Lectures

Events By Interest

Academic

Events By Audience

Public

Events By School

School of Science

Tags

prob_sem, aldixon

Website

https://math.mit.edu/seminars/probabi...

Department
Department of Mathematics
Hashtag

#Mathematics

Contact Email

aldixon@mit.edu

Add to my calendar

Recent Activity

You're not going yet!

This event requires registration.