A short proof that the extension complexity of the correlation polytope grows exponentially

DOI10.1007/s00454-014-9655-9zbMath1315.52021arXiv1307.3543OpenAlexW3105094916MaRDI QIDQ2340413

Volker Kaibel, Stefan Weltge

Publication date: 16 April 2015

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1307.3543

zbMATH Keywords

communication complexityextended formulationscorrelation polytopeunique disjointness

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial complexity of geometric structures (52C45)

Related Items (23)

Heuristics for exact nonnegative matrix factorization ⋮ The landscape of communication complexity classes ⋮ Extended formulations for independence polytopes of regular matroids ⋮ Average case polyhedral complexity of the maximum stable set problem ⋮ Extension complexity of low-dimensional polytopes ⋮ Boolean quadric polytopes are faces of linear ordering polytopes ⋮ Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes ⋮ Lifts for Voronoi cells of lattices ⋮ On tail dependence matrices. The realization problem for parametric families ⋮ Complexity of combinatorial optimization problems in terms of face lattices of associated polytopes ⋮ Maximum semidefinite and linear extension complexity of families of polytopes ⋮ Affine reductions for LPs and SDPs ⋮ Extended formulations for order polytopes through network flows ⋮ Extension complexity and realization spaces of hypersimplices ⋮ Disjoint pairs in set systems with restricted intersection ⋮ Information-theoretic approximations of the nonnegative rank ⋮ Unnamed Item ⋮ Exponential Lower Bounds for Polytopes in Combinatorial Optimization ⋮ Membership testing for Bernoulli and tail-dependence matrices ⋮ Extension complexity of the correlation polytope ⋮ Volume computation for sparse Boolean quadric relaxations ⋮ The biclique covering number of grids ⋮ Affine maps between quadratic assignment polytopes and subgraph isomorphism polytopes

Cites Work

• Common information and unique disjointness
• Boolean function complexity. Advances and frontiers.
• On the extension complexity of combinatorial polytopes
• Expressing combinatorial optimization problems by linear programs
• On the distributional complexity of disjointness
• A note on the extension complexity of the knapsack polytope
• The Matching Polytope has Exponential Extension Complexity
• Nondeterministic Quantum Query and Communication Complexities
• Communication Complexity
• Linear vs. semidefinite extended formulations

This page was built for publication: A short proof that the extension complexity of the correlation polytope grows exponentially