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

2013/05/14 by Jop Briët, Daniel Dadush, Briët, Jop +3
Computer Science · Mathematics · #68W25 #90C05 #90C60 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #cs.CC #math.CO #msc:68W25 #msc:90C05 #msc:90C60

paper · pdf · doi:10.48550/arxiv.1305.3268

arxiv created 2013/12/03 · arxiv updated 2013/12/04

Abstract

In Rothvoß it was shown that there exists a 0/1 polytope (a polytope whose vertices are in \0,1\ⁿ) 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 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^Ω(n) and an affine space. Our proof relies on a new technique to rescale semidefinite factorizations.

Related

• Some 0/1 polytopes need exponential size extended formulations
• Maximum Semidefinite and Linear Extension Complexity of Families of\n Polytopes
• Extension complexity of polytopes with few vertices or facets
• Complex psd-minimal polytopes in dimensions two and three
• On the extension complexity of polytopes separating subsets of the Boolean cube