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

November 19, 2013, 4:00pm
John­son 175
Daniel Dadush, Courant Insti­tute of Math­e­mat­i­cal Sci­ences, 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 poly­tope such that any higher-dimensional poly­tope pro­ject­ing to it must have an expo­nen­tial num­ber 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.

Leave a Reply

Your email address will not be published. Required fields are marked *