2013/07/31 by Volker Kaibel, Stefan Weltge · 1 citation
Mathematics · #math.CO #math.OC #msc:52Bxx #msc:90C57 #msc:94Axx
paper · pdf · doi:10.1007/s00454-014-9655-9
published as Discrete & Computational Geometry, 2015, 53 (2), pages 396--401 · 4 pages; the journal version contains a mistake in the definition of the set R_G in Lemma 2, which is fixed here
arxiv created 2016/02/25 · arxiv updated 2016/02/26
We establish that the extension complexity of the nXn 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.