A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially
A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially
复制标题
相关多胞形的可拓复杂度呈指数增长的简短证明
DOI：
10.1007/s00454-014-9655-9
复制
发表时间：
2015
影响因子：
0.8
通讯作者：
Stefan Weltge
中科院分区：
文献类型：
--
作者：
Volker Kaibel;Stefan Weltge
我们建立了相关多面体的扩张复杂性至少是通过一个简短的证明，该证明是自包含的，除了使用多面体的每个面都是它所包含的所有面的交集这一事实。证明的主要创新点是一个简单的组合论证，证明了唯一不相交矩阵的矩形覆盖数至少为，因此唯一不相交谓词的不确定通信复杂度至少为.因此，我们对以前最著名的下界和分别略有改进。
We establish that the extension complexity of thecorrelation polytope is at leastby a short proof that is self-contained except for using the fact that every face of a polyhedron is the intersection of all facets it is contained in. The main innovative aspect of the proof is a simple combinatorial argument showing that the rectangle covering number of the unique-disjointness matrix is at least, and thus the nondeterministic communication complexity of the unique-disjointness predicate is at least. We thereby slightly improve on the previously best known lower boundsand, respectively.
关于背包多面体可拓复杂度的一个注记
影响因子：
1.1
作者：
S. Pokutta;M. Vyve
通讯作者：
M. Vyve
共同信息和独特的脱节
DOI：
--
发表时间：
2013
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Gábor Braun;S. Pokutta
通讯作者：
S. Pokutta