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

ACO Student Seminar
Wednesday, August 21, 2013 - 1:00pm
1 hour (actually 50 minutes)
ISyE Executive classroom
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 semidefinite cone and an affine space? We answer this question in the affirmative using a new technique to rescale semidefinite factorizations