### On the existence of 0/1 polytopes with high semidefinite extension complexity

- Series
- ACO Student Seminar
- Time
- Wednesday, August 21, 2013 - 13:00 for 1 hour (actually 50 minutes)
- Location
- ISyE Executive classroom
- Speaker
- Daniel Dadush – Courant Institute, NYU

In 2011, Rothvoß showed that there exists a 0/1 polytope such that any higher-dimensional polytope projecting to it must have a subexponential number of facets, i.e., its linear extension complexity is subexponential. The question as to whether there exists a 0/1 polytope having high PSD extension complexity was left open, i.e. is there a 0/1 polytope such that any spectrahedron projecting to it must be the intersection of a subexponential sized semideﬁnite cone and an aﬃne space? We answer this question in the aﬃrmative using a new technique to rescale semideﬁnite factorizations