Exponential Lower Bounds for Polytopes in Combinatorial Optimization

We solve a 20-year old problem posed by Yannakakis and prove that no polynomial-size linear program (LP) exists whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the cut polytope and the stable set polytope. These results were discovered through a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs.

• Publication year

  2011

• Venue

  Journal of the ACM

• Publication date

  2011-11-03

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1145/2716307arXiv 1111.0837
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Communication Complexity

  2016cited by this paper
• Information-theoretic approximations of the nonnegative rank

  2016cited by this paper
• Lower Bounds on the Size of Semidefinite Programming Relaxations

  2014cited by this paper
• Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States

  2013cited by this paper
• Common Information and Unique Disjointness

  2013influential reference
• An information complexity approach to extended formulations

  2013influential reference
• Exponential lower bounds on fixed-size psd rank and semidefinite extension complexity

  2013cited by this paper
• On the extension complexity of combinatorial polytopes

  2013influential reference
• Approximate Constraint Satisfaction Requires Large LP Relaxations

  2013cited by this paper
• Generalized probabilistic theories and conic extensions of polytopes

  2013cited by this paper
• A note on the extension complexity of the knapsack polytope

  2013cited by this paper
• A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially

  2013influential reference
• On the existence of 0/1 polytopes with high semidefinite extension complexity

  2013cited by this paper
• Average case polyhedral complexity of the maximum stable set problem

  2013influential reference
• The matching polytope has exponential extension complexity

  2013influential reference
• Correlation/Communication complexity of generating bipartite states

  2012cited by this paper
• Symmetry Matters for Sizes of Extended Formulations

  2012cited by this paper
• Approximation Limits of Linear Programs (Beyond Hierarchies)

  2012cited by this paper
• Quantum Computation and Quantum Information

  2012cited by this paper
• Support-based lower bounds for the positive semidefinite rank of a nonnegative matrix

  2012cited by this paper
• Some 0/1 polytopes need exponential size extended formulations

  2011cited by this paper
• Extended formulations, nonnegative factorizations, and randomized communication protocols

  2011cited by this paper
• Combinatorial bounds on nonnegative rank and extended formulations

  2011cited by this paper
• Lifts of Convex Sets and Cone Factorizations

  2011influential reference
• Extended Formulations in Combinatorial Optimization

  2011cited by this paper
• Extended formulations in combinatorial optimization

  2010influential reference
• A counterexample to the Alon-Saks-Seymour conjecture and related problems

  2010cited by this paper
• Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy

  2010cited by this paper
• Quantum strategic game theory

  2010cited by this paper
• Nonlocality and communication complexity

  2010influential reference
• Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic Programming and MaxCutGain

  2010cited by this paper
• Quantum Proofs for Classical Theorems

  2009cited by this paper
• Optimal Sherali-Adams Gaps from Pairwise Independence

  2009cited by this paper
• Reformulation and Decomposition of Integer Programs

  2009cited by this paper
• Geometry of cuts and metrics

  2009cited by this paper
• On the complexity of communication complexity

  2009cited by this paper
• Tight Lower Bounds on the Sizes of Symmetric Extensions of Permutahedra and Similar Results

  2009cited by this paper
• The Communication Complexity of Set-Disjointness with Small Sets and 0-1 Intersection

  2009cited by this paper
• Symmetry in Extended Formulations of the Permutahedron

  2009cited by this paper
• Integrality gaps for Sherali-Adams relaxations

  2009cited by this paper
• Theta Bodies for Polynomial Ideals

  2008cited by this paper
• Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut

  2007cited by this paper
• Quantum Computer Science: An Introduction

  2007cited by this paper
• One-way multiparty communication lower bound for pointer jumping with applications

  2007cited by this paper
• Lattice problems in NP ∩ coNP

  2005cited by this paper
• Lattice Problems in NP cap coNP

  2004cited by this paper
• Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?

  2004cited by this paper
• Rank bounds and integrality gaps for cutting planes procedures

  2003cited by this paper
• Lower bounds for local search by quantum arguments

  2003cited by this paper
• Combinatorial optimization. Polyhedra and efficiency.

  2003influential reference
• Semidefinite Programs and Combinatorial Optimization

  2003influential reference
• Recent advances in algorithms and combinatorics

  2003cited by this paper
• Nondeterministic Quantum Query and Communication Complexities

  2003influential reference
• Exponential lower bound for 2-query locally decodable codes via a quantum argument

  2002cited by this paper
• Quantum communication and complexity

  2002cited by this paper
• Proving integrality gaps without knowing the linear program

  2002cited by this paper
• Clique is hard to approximate withinn1−ε

  1999cited by this paper
• Clique Is Hard to Approximate within N 1?

  1997cited by this paper
• Communication Complexity

  1997cited by this paper
• Clique is hard to approximate within n 1 − ǫ

  1996cited by this paper
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

  1995influential reference
• Lectures on Polytopes

  1994cited by this paper
• Communication Complexity and Combinatorial Lattice Theory

  1993cited by this paper
• A lift-and-project cutting plane algorithm for mixed 0–1 programs

  1993cited by this paper
• Convex analysis and minimization algorithms

  1993cited by this paper
• Combinatorial Optimization

  1992cited by this paper
• Expressing combinatorial optimization problems by linear programs

  1991influential reference
• Cones of Matrices and Set-Functions and 0-1 Optimization

  1991cited by this paper
• On the Distributional Complexity of Disjointness

  1990influential reference
• A Hierarchy of Relaxations Between the Continuous and Convex Hull Representations for Zero-One Programming Problems

  1990cited by this paper
• A hierarchy of relaxation between the continuous and convex hull representations

  1990cited by this paper
• The cut polytope and the Boolean quadric polytope

  1990cited by this paper
• Introduction to the theory of computation

  1989cited by this paper
• Disjunctive programming and a hierarchy of relaxations for discrete optimization problems

  1985cited by this paper
• A new polynomial-time algorithm for linear programming

  1984cited by this paper
• Polynomial algorithms in linear programming

  1980cited by this paper
• A polynomial algorithm in linear programming

  1979cited by this paper
• On the Shannon capacity of a graph

  1979influential reference
• The synthesis of two-terminal switching circuits

  1949cited by this paper

• Min-Max Connected Multiway Cut

  2026cites this paper
• Equiprojective polytopes in higher dimension

  2026cites this paper
• Vanishing of Schubert coefficients is in AM ∩ coAM assuming the GRH

  2025cites this paper
• Efficient Compilation of Algorithms into Compact Linear Programs

  2025cites this paper
• Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width

  2025cites this paper
• Measurement incompatibility and quantum steering via linear programming

  2025cites this paper
• Negations are powerful even in small depth

  2025influential citation
• Binary Cyclic Transversal Polytopes

  2024influential citation
• Neural Networks and (Virtual) Extended Formulations

  2024cites this paper
• Piecewise Polyhedral Relaxations of Multilinear Optimization

  2024cites this paper
• Optimal Extended Formulations from Optimal Dynamic Programming Algorithms

  2024cites this paper
• Sum of Squares Circuits

  2024cites this paper
• Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack

  2023influential citation
• Trade-offs between Entanglement and Communication

  2023cites this paper
• On modeling NP-Complete problems as polynomial-sized linear programs: Escaping/Side-stepping the "barriers"

  2023influential citation
• Matrix factorization ranks via polynomial optimization

  2023cites this paper
• Around the log-rank conjecture

  2023cites this paper
• One Clean Qubit Suffices for Quantum Communication Advantage

  2023cites this paper
• Subtractive Mixture Models via Squaring: Representation and Learning

  2023influential citation
• Polytopes with Bounded Integral Slack Matrices Have Sub-Exponential Extension Complexity

  2023cites this paper
• Synergies Between Operations Research and Quantum Information Science

  2023cites this paper
• Circuits in extended formulations

  2022cites this paper
• The role of rationality in integer-programming relaxations

  2022cites this paper
• On Semi-Algebraic Proofs and Algorithms

  2022cites this paper
• PIECEWISE POLYHEDRAL RELAXATIONS OF MULTILINEAR

  2022cites this paper
• Lifts for Voronoi Cells of Lattices

  2021cites this paper
• A Non-commutative Extension of Lee-Seung's Algorithm for Positive Semidefinite Factorizations

  2021cites this paper
• On the Extension Complexity of Polytopes Separating Subsets of the Boolean Cube

  2021cites this paper
• Pitch, extension complexity, and covering problems

  2021cites this paper
• Positive spectrahedrons: Geometric properties, Invariance principles and Pseudorandom generators

  2021cites this paper
• Convexification of Permutation-Invariant Sets and an Application to Sparse Principal Component Analysis

  2021cites this paper
• Complex psd-minimal polytopes in dimensions two and three

  2021cites this paper
• Differentiable Equilibrium Computation with Decision Diagrams for Stackelberg Models of Combinatorial Congestion Games

  2021cites this paper
• Multiplicative updates for symmetric-cone factorizations

  2021cites this paper
• Extended formulations for matroid polytopes through randomized protocols

  2021cites this paper
• Worst-case analysis of clique MIPs

  2021cites this paper
• Positive spectrahedra: invariance principles and pseudorandom generators

  2021cites this paper
• On the complexity of computing a random Boolean function over the reals

  2020cites this paper
• On the Complexity of Some Facet-Defining Inequalities of the QAP-polytope

  2020cites this paper
• Separation routine and extended formulations for the stable set problem in claw-free graphs

  2020cites this paper
• Communication memento: Memoryless communication complexity

  2020cites this paper
• Lifting for Simplicity: Concise Descriptions of Convex Sets

  2020cites this paper
• Sparktope: linear programs from algorithms

  2020cites this paper
• Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach

  2020cites this paper
• References

  2020cites this paper
• Extension complexity of low-dimensional polytopes

  2020cites this paper
• Mathematics and Computation

  2019cites this paper
• The log-approximate-rank conjecture is false

  2019cites this paper
• Nonnegative rank measures and monotone algebraic branching programs

  2019cites this paper
• On modeling hard combinatorial optimization problems as linear programs: Refutations of the "unconditional impossibility" claims

  2019influential citation
• On the extension complexity of scheduling

  2019cites this paper
• Convexification of Permutation-Invariant Sets and Applications.

  2019cites this paper
• Tensor decompositions on simplicial complexes with invariance

  2019cites this paper
• Simulated Annealing Approach to Verify Vertex Adjacencies in the Traveling Salesperson Polytope

  2019cites this paper
• On a conditional inequality in Kolmogorov complexity and its applications in communication complexity

  2019cites this paper
• Convexification of Permutation-Invariant Sets and an Application to Sparse PCA

  2019cites this paper
• Representations of Monotone Boolean Functions by Linear Programs

  2019cites this paper
• Limitations of the Hyperplane Separation Technique for Bounding the Extension Complexity of Polytopes

  2019cites this paper
• On Vertices of the Simple Boolean Quadric Polytope Extension

  2018cites this paper
• CSE 291 : Communication Complexity , Winter 2019 Deterministic protocols

  2018influential citation
• Limits of Treewidth-based tractability in Optimization

  2018cites this paper
• Parameterized low-rank binary matrix approximation

  2018cites this paper
• Lower Bounds for Interactive Compression and Linear Programs

  2018cites this paper
• Randomized Communication versus Partition Number

  2018cites this paper
• New limits of treewidth-based tractability in optimization

  2018cites this paper
• On polyhedral approximations of the positive semidefinite cone

  2018cites this paper
• From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems

  2018cites this paper
• Extension Complexity of the Correlation Polytope

  2018cites this paper
• On the nature of the Theory of Computation (ToC)

  2018cites this paper
• Affine maps between graph isomorphism polytopes and Boolean quadratic polytopes

  2017influential citation
• On the linear extension complexity of stable set polytopes for perfect graphs

  2017cites this paper
• Boolean quadric polytopes are faces of linear ordering polytopes

  2017cites this paper
• Strengthening convex relaxations of 0/1-sets using Boolean formulas

  2017cites this paper
• On the Combinatorial Lower Bound for the Extension Complexity of the Spanning Tree Polytope

  2017cites this paper
• Boolean quadric polytopes are faces of linear ordering polytopes ∗

  2017cites this paper
• Extension Complexity of Stable Set Polytopes of Bipartite Graphs

  2017influential citation
• Lower Bounds for Approximating the Matching Polytope

  2017cites this paper
• Lifting Linear Extension Complexity Bounds to the Mixed-Integer Setting

  2017cites this paper
• Polynomial Proof Systems, Effective Derivations, and their Applications in the Sum-of-Squares Hierarchy

  2017cites this paper
• The Rectangle Covering Number of Random Boolean Matrices

  2017cites this paper
• Lower Bounds on Matrix Factorization Ranks via Noncommutative Polynomial Optimization

  2017cites this paper
• Balas formulation for the union of polytopes is optimal

  2017cites this paper
• Affine maps between quadratic assignment polytopes and subgraph isomorphism polytopes

  2017influential citation
• Research on Weighing Strategy of Vehicle Entering Plant Based on Fuzzy Operation Time

  2017cites this paper
• Extended Formulations for Order Polytopes through Network Flows.

  2017cites this paper
• Volume computation for sparse Boolean quadric relaxations

  2017cites this paper
• A reduction framework for approximate extended formulations and a faster algorithm for convex optimization

  2017cites this paper
• Some Problems Related to Extensions of Polytopes

  2017cites this paper
• Treewidth, Extended Formulations of CSP and MSO Polytopes, and their Algorithmic Applications

  2017cites this paper
• Extension Complexity and Realization Spaces of Hypersimplices

  2017cites this paper
• Completely positive semidefinite rank

  2017cites this paper
• Analysis of Algebraic complexity classes and boolean functions [HBNI Th106]

  2016cites this paper
• Euclidean Distance Matrices and Separations in Communication Complexity Theory

  2016cites this paper
• Polyhedral results and a branch-and-cut algorithm for the double traveling Salesman problem with multiple stacks

  2016cites this paper
• 15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016, Reykjavik, Iceland, June 22-24, 2016

  2016cites this paper
• The Parity Hamiltonian Cycle Problem in Directed Graphs

  2016cites this paper
• Polyhedral Analysis of Up-peak Traffic Patterns in Elevator Dispatching Problem

  2016cites this paper
• Discrete Optimization and Operations Research

  2016influential citation
• On Integer Recognition over Some Boolean Quadric Polytope Extension

  2016cites this paper
• On the sum-of-squares degree of symmetric quadratic functions

  2016cites this paper