A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially

Volker Kaibel; Stefan Weltge

doi:10.1007/s00454-014-9655-9

A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially

Volker Kaibel, Stefan Weltge

Otto-von-Guericke University

Research output: Contribution to journal › Article › peer-review

30 Scopus citations

Abstract

We establish that the extension complexity of the n ×n correlation polytope is at least 1.5ⁿ by 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 1.5ⁿ, and thus the nondeterministic communication complexity of the unique-disjointness predicate is at least .58n. We thereby slightly improve on the previously best known lower bounds 1.24ⁿ and .31n, respectively.

Original language	English
Pages (from-to)	397-401
Number of pages	5
Journal	Discrete and Computational Geometry
Volume	53
Issue number	2
DOIs	https://doi.org/10.1007/s00454-014-9655-9
State	Published - Mar 2015
Externally published	Yes

Keywords

Communication complexity
Correlation polytope
Extended formulations
Unique disjointness

Access to Document

10.1007/s00454-014-9655-9

Cite this

@article{3a2494ee850e40608a09a87811791e38,

title = "A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially",

abstract = "We establish that the extension complexity of the n ×n correlation polytope is at least 1.5n by 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 1.5n, and thus the nondeterministic communication complexity of the unique-disjointness predicate is at least .58n. We thereby slightly improve on the previously best known lower bounds 1.24n and .31n, respectively.",

keywords = "Communication complexity, Correlation polytope, Extended formulations, Unique disjointness",

author = "Volker Kaibel and Stefan Weltge",

note = "Publisher Copyright: {\textcopyright} 2014, Springer Science+Business Media New York.",

year = "2015",

month = mar,

doi = "10.1007/s00454-014-9655-9",

language = "English",

volume = "53",

pages = "397--401",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially

AU - Kaibel, Volker

AU - Weltge, Stefan

PY - 2015/3

Y1 - 2015/3

N2 - We establish that the extension complexity of the n ×n correlation polytope is at least 1.5n by 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 1.5n, and thus the nondeterministic communication complexity of the unique-disjointness predicate is at least .58n. We thereby slightly improve on the previously best known lower bounds 1.24n and .31n, respectively.

AB - We establish that the extension complexity of the n ×n correlation polytope is at least 1.5n by 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 1.5n, and thus the nondeterministic communication complexity of the unique-disjointness predicate is at least .58n. We thereby slightly improve on the previously best known lower bounds 1.24n and .31n, respectively.

KW - Communication complexity

KW - Correlation polytope

KW - Extended formulations

KW - Unique disjointness

UR - http://www.scopus.com/inward/record.url?scp=84925520201&partnerID=8YFLogxK

U2 - 10.1007/s00454-014-9655-9

DO - 10.1007/s00454-014-9655-9

M3 - Article

AN - SCOPUS:84925520201

SN - 0179-5376

VL - 53

SP - 397

EP - 401

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 2

ER -

A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this