On the existence of 0/1 polytopes with high semidefinite extension complexity
From MaRDI portal
Publication:745683
DOI10.1007/S10107-014-0785-XzbMATH Open1325.90066arXiv1305.3268OpenAlexW1858857015MaRDI QIDQ745683FDOQ745683
Daniel Dadush, Sebastian Pokutta, Jop Briët
Publication date: 14 October 2015
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: In Rothvoss{} 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^{Omega(n)} facets, i.e., its linear extension complexity is exponential. The question whether there exists a 0/1 polytope with high PSD 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^{Omega(n)} and an affine space. Our proof relies on a new technique to rescale semidefinite factorizations.
Full work available at URL: https://arxiv.org/abs/1305.3268
Combinatorial optimization (90C27) Semidefinite programming (90C22) Integer programming (90C10) Boolean programming (90C09)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Perturbation theory for linear operators.
- Expressing combinatorial optimization problems by linear programs
- Linear vs. semidefinite extended formulations
- On Polyhedral Approximations of the Second-Order Cone
- Extended formulations for polygons
- Lifts of Convex Sets and Cone Factorizations
- The Matching Polytope has Exponential Extension Complexity
- Smallest compact formulation for the permutahedron
- Some \(0/1\) polytopes need exponential size extended formulations
- Common information and unique disjointness
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- An information complexity approach to extended formulations
- Extended formulations, nonnegative factorizations, and randomized communication protocols
Cited In (11)
- Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations
- Maximum semidefinite and linear extension complexity of families of polytopes
- No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ
- Title not available (Why is that?)
- On polyhedral extension of some LP theorems
- The matching problem has no small symmetric SDP
- Extension complexity of formal languages
- New limits of treewidth-based tractability in optimization
- On the extension complexity of polytopes separating subsets of the Boolean cube
- On the NP-hardness of deciding emptiness of the split closure of a rational polytope in the 0,1 hypercube
- Affine reductions for LPs and SDPs
This page was built for publication: On the existence of 0/1 polytopes with high semidefinite extension complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q745683)
