November 19, 2013, 4:00pm
Daniel Dadush, Courant Institute of Mathematical Sciences, NYU.
On the existence of 0/1 polytopes with high semidefinite extension complexity
Abstract: In linear programming, the technique of linear extended formulations attempts to translate exponential sized linear programs into polynomial sized ones. To do this, one finds a higher dimensional polytope with relatively few facets that projects to the original feasible polytope. The technique has limitations, however. In 2011, Rothvoss showed that there exists a 0/1 polytope such that any higher-dimensional polytope projecting to it must have an exponential number of facets, i.e., there does not exist a polynomial sized linear extended formulation. The technique of linear extended formulations can be generalized to PSD extended formulations by working with PSD cones instead of nonnegative orthants. Using new techniques to rescale semidefinite factorizations, we show that there exists a 0/1 polytope such that every PSD extended formulation for this polytope must have exponential size.
Joint work with Jop Briet and Sebastian Pokutta.