On the existence of 0/1 polytopes with high semidefinite extension complexity
成果类型：
Article
署名作者：
Briet, Jop; Dadush, Daniel; Pokutta, Sebastian
署名单位：
New York University; University System of Georgia; Georgia Institute of Technology
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-014-0785-x
发表日期：
2015
页码：
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 ) such that any higher-dimensional polytope projecting to it must have 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 and an affine space. Our proof relies on a new technique to rescale semidefinite factorizations.
来源URL：