2015-01-01

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

## Publication

### Publication

*Mathematical Programming , Volume 153 - Issue 1 p. 179- 199*

In Rothvoß (Math Program 142(1–2):255–268, 2013) it was shown that
there exists a 0/1 polytope (a polytope whose vertices are in {0, 1}n) such that any
higher-dimensional polytope projecting to it must have 2Ω(n) facets, i.e., its linear
extension complexity is exponential. The question whether there exists a 0/1 polytope
with high positive semidefinite extension complexity was left open. We answer this
question in the affirmative by showing that there is a 0/1 polytope such that any spectrahedron
projecting to it must be the intersection of a semidefinite cone of dimension
2Ω(n) and an affine space. Our proof relies on a new technique to rescale semidefinite
factorizations.

Additional Metadata | |
---|---|

THEME | Logistics (theme 3) |

Publisher | Springer |

Persistent URL | dx.doi.org/10.1007/s10107-014-0785-x |

Journal | Mathematical Programming |

Citation |
Briët, J, Dadush, D.N, & Pokutta, S. (2015). On the existence of 0/1 polytopes with high semidefinite extension complexity.
Mathematical Programming, 153(1), 179–199. doi:10.1007/s10107-014-0785-x |