Optimization Online


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

Volker Kaibel(kaibel***at***ovgu.de)
Stefan Weltge(weltge***at***ovgu.de)

Abstract: We establish that the extension complexity of the nXn correlation polytope is at least 1.5^n 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^n, and thus the nondeterministic communication complexity of the unique-disjointness predicate is at least .58n.

Keywords: lower bound, extension complexity, correlation polytope, unique disjointness, nondeterministic communication complexity

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: August 2013

Download: [PDF]

Entry Submitted: 09/10/2013
Entry Accepted: 09/10/2013
Entry Last Modified: 09/10/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society