On the existence of 0/1 polytopes with high semidefinite extension complexity
From MaRDI portal
(Redirected from Publication:745683)
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.
Recommendations
- On the existence of 0/1 polytopes with high semidefinite extension complexity
- Maximum semidefinite and linear extension complexity of families of polytopes
- Some \(0/1\) polytopes need exponential size extended formulations
- On polyhedral approximations of the positive semidefinite cone
- Lower bounds on the size of semidefinite programming relaxations
Cites work
- scientific article; zbMATH DE number 1466163 (Why is no real title available?)
- scientific article; zbMATH DE number 1538119 (Why is no real title available?)
- scientific article; zbMATH DE number 3052220 (Why is no real title available?)
- An information complexity approach to extended formulations
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- Common information and unique disjointness
- Expressing combinatorial optimization problems by linear programs
- Extended formulations for polygons
- Lifts of Convex Sets and Cone Factorizations
- Linear vs. semidefinite extended formulations
- On Polyhedral Approximations of the Second-Order Cone
- Perturbation theory for linear operators.
- Smallest compact formulation for the permutahedron
- Some \(0/1\) polytopes need exponential size extended formulations
Cited in
(12)- On the complexity of computing a random Boolean function over the reals
- Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations
- Maximum semidefinite and linear extension complexity of families of polytopes
- The matching problem has no small symmetric SDP
- On polyhedral extension of some LP theorems
- Extension complexity of formal languages
- No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
- New limits of treewidth-based tractability in optimization
- On the NP-hardness of deciding emptiness of the split closure of a rational polytope in the 0,1 hypercube
- On the existence of 0/1 polytopes with high semidefinite extension complexity
- On the extension complexity of polytopes separating subsets of the Boolean cube
- 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)
