When faced with an NP-hard combinatorial optimization problem, a standard algorithmic strategy is to relax it into a continuous optimization problem, such as a Linear Program (LP) or a Semidefinite Program (SDP). To solve the problem exactly, we would ideally optimize over the convex hull of all valid solutions—a geometric object known as the problem's polytope.
The catch is that for hard problems, these polytopes typically have an exponential number of facets (inequalities) in their native space, making direct optimization intractable. However, optimization designers have a clever workaround: extended formulations. By introducing auxiliary variables, we can "lift" the polytope into a higher-dimensional space where it might require far fewer facets, and then project it back down to our original space.
The minimum number of constraints required to represent a shape in this higher-dimensional space is called its extension complexity. This framework raises a profound theoretical question: can the geometric power of lifting allow us to solve NP-hard problems using polynomial-sized linear or semidefinite programs?
The Slack Matrix and the Limits of Linear Lifting
To prove that a polytope cannot be simplified via lifting, we need a way to translate geometry into linear algebra. This bridge is provided by the slack matrix.
For a given polytope $P$, the slack matrix $S$ records the "slack" or distance between every single vertex $v$ and every facet-defining inequality $A_i x \le b_i$. Specifically, the entry $S_{i,v} = b_i - A_i v$. In a foundational result, Yannakakis proved that the linear extension complexity of a polytope is exactly equal to the nonnegative rank of its slack matrix—the minimum number of rank-1 nonnegative matrices needed to sum up to $S$.
As explained by Tim Roughgarden in Communication Complexity (for Algorithm Designers), this algebraic equivalence allows us to use tools from communication complexity to prove lower bounds on optimization size. If two parties try to compute the entries of the slack matrix with minimal communication, their randomized communication complexity lower-bounds the nonnegative rank.
Using these geometric and communication-theoretic insights, Samuel Fiorini et al. settled a long-standing open problem in Exponential Lower Bounds for Polytopes in Combinatorial Optimization. The authors proved that the Traveling Salesperson Problem (TSP) polytope has an exponential linear extension complexity. This unconditionally ruled out the existence of any polynomial-sized LP relaxation for TSP, even when using arbitrary auxiliary variables.
Native Space (Exponential Facets) ---> Lifted Space (Polynomial Facets)
[Hard to Optimize] [Easy to Optimize]
^ |
| v
+--- Projection maps it back -----------+
This barrier is not unique to NP-hard problems. In The Exact Bipartite Matching Polytope Has Exponential Extension Complexity, Ola Svensson et al. demonstrated that even certain constrained variants of the perfect matching problem—which is otherwise solvable in polynomial time—inherently require exponential linear extended formulations.
The Semidefinite Advantage and PSD Rank
Semidefinite programming offers a massive upgrade over linear programming. Instead of projecting a higher-dimensional polyhedron (defined by scalar inequalities), an SDP projects a spectrahedron—a shape defined by linear matrix inequalities, where a matrix is constrained to be positive semidefinite (PSD).
Mathematically, this shifts our algebraic metric from nonnegative rank to positive semidefinite (PSD) rank. To find the semidefinite extension complexity of a polytope, we look for the minimum dimension $r$ such that each entry of the slack matrix can be factored into the trace inner product of two $r \times r$ PSD matrices: $S_{i,v} = \text{Tr}(A_i B_v)$.
Because PSD matrices can compactly encode non-linear, curved geometric relationships, they can be exponentially more efficient than linear constraints. Samuel Fiorini et al. proved this separation rigorously in Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds, establishing that certain geometric families exhibit an exponential gap between their linear and semidefinite extension complexities.
Similarly, Hamza Fawzi and Pablo Parrilo demonstrated in Sparse sum-of-squares certificates on finite abelian groups that structured geometric objects, such as cyclic polytopes, enjoy a provable efficiency advantage when represented via semidefinite formulations rather than traditional linear constraints.
Unconditional Lower Bounds for SDPs
Given that SDPs are exponentially more expressive than LPs, could they potentially compress the TSP or Max Cut polytopes down to a polynomial size? Proving lower bounds on PSD rank is notoriously difficult because the space of PSD matrices lacks the rigid, coordinate-wise structure of nonnegative vectors.
The breakthrough that allowed researchers to bound general SDP size came from establishing an equivalence between arbitrary SDP relaxations and canonical hierarchical proof systems—specifically, the Sum-of-Squares (SoS) hierarchy.
In Lower bounds on the size of semidefinite programming relaxations, James R. Lee et al. proved that for Constraint Satisfaction Problems (CSPs), any arbitrary polynomial-sized SDP relaxation is fundamentally no more powerful than a static, few-round instance of the SoS hierarchy. By leveraging known lower bounds for the SoS hierarchy, the authors proved the first super-polynomial lower bounds on the semidefinite extension complexity of classic problems like Max Cut and TSP. This confirmed that the geometric flexibility of spectrahedra still cannot circumvent NP-hardness.
To prove that this limitation is an inherent geometric property of combinatorial spaces rather than a specific quirk of TSP or Max Cut, Jop Briët et al. developed a counting argument in On the existence of 0/1 polytopes with high semidefinite extension complexity. By measuring the volume of the space of small spectrahedra, the authors proved that the vast majority of all $0/1$-polytopes require an exponential semidefinite extension complexity.
The Cost of Symmetry
When algorithm designers build LP or SDP relaxations, they almost always construct symmetric formulations. If a graph problem is invariant under a permutation of its vertices, the corresponding mathematical program should share that same permutation invariance. Symmetry makes relaxations intuitive to write down and analyze, but it comes at a steep cost.
[Problem Symmetry] ---> Forces ---> [Symmetric SDP Formulation] ---> Inflates ---> [Extension Complexity]
In The matching problem has no small symmetric SDP, Gábor Braun et al. analyzed what happens when we restrict our optimization to symmetric extended formulations. They proved that the perfect matching problem requires an exponential size to be represented or even closely approximated by a symmetric SDP.
Because perfect matching can be solved efficiently in polynomial time using Edmonds' blossom algorithm, this result reveals a striking paradox: a problem can be computationally easy, yet its symmetric semidefinite extension complexity can be exponentially large. Symmetry constraints can artificially inflate the size of a formulation, meaning that asymmetric or unstructured relaxations are sometimes required to achieve optimal efficiency.
Approximations and the Frontier
Modern research focuses heavily on approximate extension complexity. We may accept that an exact polynomial-sized SDP for an NP-hard problem is impossible, but can a small SDP approximate the true solution within a tight factor (e.g., approximating Max Cut within the Goemans-Williamson ratio of $0.878$)?
As shown by Siu On Chan et al. in Approximate Constraint Satisfaction Requires Large LP Relaxations, small linear programs are strictly bounded by the Sherali-Adams linear hierarchy when approximating CSPs. Translating these approximate lower bounds fully to the semidefinite and SoS setting remains a central challenge. By mapping out the exact boundaries of PSD rank and spectrahedral projections, this line of research continues to map the fundamental limits of what convex optimization can achieve.
Key Foundational Work
Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds (2011) — contributed 4 concept elements to this direction.
Proving Integrality Gaps without Knowing the Linear Program (2006) — contributed 1 concept elements to this direction.