Source-linked AI summary
Exponential Lower Bounds for Polytopes in Combinatorial Optimization
Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf
TL;DR
The paper asks whether polynomial-size LPs can represent the TSP and related polytopes without symmetry restrictions. It answers this using connections among extension formulations, communication protocols, and semidefinite factorizations, obtaining unconditional super-polynomial lower bounds. The results also reveal exponential separations between classical and quantum factorization measures while leaving semidefinite formulations of the cut polytope unresolved.
Problem
Whether the TSP, cut, and stable set polytopes admit polynomial-size LP formulations remained unresolved, including the unrestricted TSP case after symmetric formulations were ruled out.
Method
The paper connects LP and semidefinite extension formulations to classical and one-way quantum communication protocols through nonnegative and PSD factorizations.
Results
The paper proves unconditional super-polynomial lower bounds for LP formulations of the cut, stable set, and TSP polytopes, and establishes an exponential separation between nonnegative rank and PSD rank.
Takeaways & Limitations
These results rule out polynomial-size LP approaches for the three explicit polytopes while showing that semidefinite formulations can behave differently from linear ones.
Takeaways & Limitations
The paper leaves open whether the cut polytope has a polynomial-size semidefinite extended formulation.
Abstract
from arXiv · showhide
We solve a 20-year old problem posed by Yannakakis and prove that there exists no polynomial-size linear program (LP) 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.
1 Introduction
The paper resolves Yannakakis’s open question by proving unconditional super-polynomial lower bounds for LP formulations of several explicit combinatorial polytopes. Its approach connects extension formulations and communication complexity with one-way quantum protocols and semidefinite factorizations.
- Main contribution: The paper proves super-polynomial lower bounds for every LP formulation of the TSP, cut, and stable set polytopes.These bounds are unconditional and rule out polynomial-size LPs for expressing the three problems.
- State of the art: Yannakakis proved a 2^Ω(n) lower bound for symmetric TSP formulations, but whether asymmetry helps remained open.The paper addresses the unrestricted extension complexity of the TSP polytope.
- Main contribution: A 2^n×2^n matrix with nonnegative rank 2^Ω(n) yields a 2^Ω(n) lower bound for the cut polytope and reductions to stable set and TSP polytopes.The nonnegative-rank lower bound follows from Ω(n) nondeterministic communication complexity of the matrix’s support.
- Quantum connection: The paper establishes a tight connection between semidefinite extension formulations and one-way quantum communication protocols.Rank-r PSD factorizations correspond to protocols using log r + O(1) qubits, while q-qubit protocols yield PSD rank 2^q.
- Quantum connection: A protocol computing entry-wise squares of rank-r matrices gives a log r + O(1)-qubit protocol and an O(d)-size semidefinite formulation for d-dimensional 0/1-slack polytopes.The construction provides an efficient PSD factorization even when the associated nonnegative rank is exponentially larger.
- Interpretation: The resulting classical lower bounds were obtained by first finding efficient PSD factorizations, linking the proof strategy to quantum considerations.This reverses the usual direction in which communication lower bounds are used to derive formulation lower bounds.
2 A Simple Matrix with Large Rectangle Covering Bound
The paper constructs a 2^n×2^n matrix whose support matrix requires exponentially many monochromatic rectangles. This rectangle-covering lower bound supplies the communication-complexity ingredient for later extension-complexity bounds.
- Matrix construction: The matrix M(n) has rows and columns indexed by n-bit strings and nonnegative real entries.Its support matrix records whether each entry of M is nonzero.
- Matrix construction: The matrix can be represented using the Frobenius inner product and diagonal matrices formed from the indexing strings.This representation is used to verify the matrix identity and support its later factorization analysis.
- Rectangle covering: A rectangle is a Cartesian product of row and column index sets, and monochromatic rectangles cover 1-entries of the support matrix.Such covers correspond to nondeterministic communication protocols for the associated Boolean function.
- Rectangle covering: 2^Ω(n) 1-monochromatic rectangles are required to cover the support matrix of M.Equivalently, the associated function has nondeterministic communication complexity Ω(n) bits.
- Rectangle covering: The lower bound follows from sets A and B separated by the inner product predicate, together with a distribution assigning mass 3/4 to A and exponentially limiting each rectangle’s mass.For sufficiently large n, the constants can be taken as α = 1/135 and δ = 0.017.
3 Strong Lower Bounds on Extension Complexity
The section connects extension complexity to nonnegative factorizations of slack matrices, then applies this framework to derive strong lower bounds for cut, stable set, and traveling salesman polytopes.
- 3.2 Cut and Correlation Polytopes: The cut polytope has extension complexity 2^Ω(n), established by relating a slack-matrix submatrix to a matrix with large nonnegative rank.The section states this as an exponential lower bound on every linear extended formulation of CUT(n).
- 3.1 The Factorization Theorem: Any extension of a polytope yields a linear extended formulation, and its size is measured by the number of defining inequalities.An extension is a polytope that projects linearly onto the target polytope.
- 3.1 The Factorization Theorem: The factorization theorem states that a polytope’s extension complexity equals the nonnegative rank of its slack matrix.It equivalently characterizes bounded-size slack factorizations, extensions, and extended formulations.
- 3.1 The Factorization Theorem: Nonnegative-rank lower bounds can be obtained from submatrices of slack matrices, including through rectangle-covering bounds for their support matrices.The argument also permits redundant inequalities and implied systems when constructing the relevant slack matrices.
- 3.3 Stable Set Polytopes: For stable sets, a graph H_n with O(n^2) vertices has a face of its stable set polytope that is an extension of COR(n).A linear projection maps the constructed face onto the correlation polytope.
- 3.4 TSP Polytopes: For TSP, a formula-based directed graph construction makes tours correspond to satisfying assignments, yielding a face of TSP(q) that extends COR(n) for q = O(n^2).This reduction implies extension complexity 2^Ω(n^1/2) for TSP(n).
4 Quantum Communication and PSD Factorizations
The section establishes equivalences among semidefinite extensions, PSD factorizations, and one-way quantum protocols computing matrices in expectation. It then derives an efficient quantum construction for squared low-rank matrices and an exponential quantum–classical separation.
- Quantum protocols and PSD factorizations: The equivalence connects quantum communication complexity to semidefinite extension complexity through the slack matrix.The construction uses PSD matrices and their trace/Frobenius products to match matrix entries in expectation.
- Semidefinite extensions and PSD factorizations: A semidefinite extension of size r is equivalent to a rank-r PSD factorization of the polytope’s slack matrix.This links semidefinite extension complexity to PSD rank through slack-matrix factorizations.
- Quantum protocols and PSD factorizations: A one-way quantum protocol with r-dimensional messages yields a rank-r PSD factorization, while a rank-r PSD factorization yields a protocol with (r + 1)-dimensional messages.The protocol computes the matrix in expectation, with messages represented by quantum states and Bob’s measurements by a POVM.
- A general upper bound: A nonnegative matrix M whose entries are the entry-wise squares of a rank-r matrix N has a one-way quantum protocol using (r + 1)-dimensional pure-state messages.The protocol follows by converting a rank-r factorization of N into a rank-r PSD factorization of M.
- A general upper bound: Every d-dimensional polytope with a 0/1 slack matrix has semidefinite extension complexity at most d + 2.Its slack matrix has rank at most d + 1, enabling the squared low-rank construction.
- Quantum versus classical communication: For each n, a matrix can be computed with log n + O(1) qubits quantumly, whereas classical randomized protocols require Ω(n) bits.This yields an exponential separation between PSD rank and nonnegative rank.
5 Concluding Remarks
The paper establishes strong extension-complexity results while identifying further questions about semidefinite formulations and communication complexity.
- The rectangle covering bound yields strong extension-complexity results and can be super-polynomial in both polytope dimension and the logarithm of its vertex count.This settles an open problem concerning the strength of the rectangle covering bound in extension-formulation settings.
- The exponential separation between nonnegative rank and PSD rank implies exponential extension complexity for every polytope between CUT(n) and Q(n).A low-complexity spectrahedron nevertheless contains CUT(n) and is contained in Q(n).
- Whether the perfect matching polytope has a polynomial-size linear extended formulation remains open because the rectangle-covering-based argument does not yield a super-polynomial lower bound there.Yannakakis had already shown exponential size for symmetric formulations of this polytope.
- Open directions include finding an exponential nonnegative-rank–PSD-rank gap and proving that the cut polytope has no polynomial-size semidefinite extended formulation.The latter would rule out SDP-based algorithms for optimizing over the cut polytope.
- The paper’s communication-complexity perspective relates the log-rank conjecture to efficiently classically simulating one-way quantum protocols for Boolean matrices.For non-Boolean matrices, the paper exhibits an exponential separation between classical and quantum protocols.
A Background on Polytopes
This background defines polytopes through convex hulls and halfspaces, then characterizes their vertices, facets, and descriptions by linear inequalities.
- A polytope is the convex hull of a finite point set, equivalently a bounded intersection of finitely many closed halfspaces.
- A valid halfspace contains the polytope, while a face is the polytope or its intersection with a valid hyperplane.
- Vertices are minimal nonempty faces, and facets are maximal proper faces of a polytope.
- Every convex-hull representation contains all vertices, and every full-dimensional linear description contains all facet-defining inequalities up to positive scaling.
- For non-full-dimensional polytopes, descriptions additionally require equalities defining the affine hull.
- A 0/1-polytope is the convex hull of a subset of {0, 1}^d, and a polyhedron is a polytope exactly when it is bounded.