- Series
- ACO Student Seminar
- Time
- Wednesday, August 21, 2013 - 1:00pm for 1 hour (actually 50 minutes)
- Location
- ISyE Executive classroom
- Speaker
- Daniel Dadush – Courant Institute, NYU – http://cs.nyu.edu/~dadush/
- Organizer
- Cristóbal Guzmán
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