Source-linked AI summary
Lower bounds on the size of semidefinite programming relaxations
James R. Lee, Prasad Raghavendra, David Steurer
TL;DR
The paper addresses how powerful polynomial-size SDP relaxations can be for hard combinatorial optimization and develops lower bounds against general SDP formulations. It connects arbitrary SDPs to low-degree sum-of-squares relaxations, showing that polynomial-size SDPs cannot surpass key approximation limits for constraint satisfaction problems.
Problem
The paper asks whether general SDP relaxations can provide arbitrarily good approximations to NP-hard problems, a goal viewed as unlikely under P ≠ NP.
Method
The paper proves lower bounds through positive semidefinite rank and characterizes low-degree sum-of-squares relaxations as optimal among polynomial-size SDP relaxations for constraint satisfaction problems.
Results
Polynomial-size SDP relaxations cannot achieve better than a 7/8-approximation for max 3-sat, while low-degree sum-of-squares relaxations are optimal among polynomial-size families for max-CSPs.
Takeaways & Limitations
For max-CSPs, increasing the variety of polynomial-size SDP relaxations beyond low-degree sum-of-squares does not improve the achievable approximation guarantees.
Takeaways & Limitations
The discussion in this section restricts the constraint-satisfaction results to optimization problems over the discrete cube, with some results applying to other problems only in restricted settings.
Abstract
from arXiv · showhide
We introduce a method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations for combinatorial problems. In particular, we show that the cut, TSP, and stable set polytopes on $n$-vertex graphs are not the linear image of the feasible region of any SDP (i.e., any spectrahedron) of dimension less than $2^{n^c}$, for some constant $c > 0$. This result yields the first super-polynomial lower bounds on the semidefinite extension complexity of any explicit family of polytopes. Our results follow from a general technique for proving lower bounds on the positive semidefinite rank of a matrix. To this end, we establish a close connection between arbitrary SDPs and those arising from the sum-of-squares SDP hierarchy. For approximating maximum constraint satisfaction problems, we prove that SDPs of polynomial-size are equivalent in power to those arising from degree-$O(1)$ sum-of-squares relaxations. This result implies, for instance, that no family of polynomial-size SDP relaxations can achieve better than a 7/8-approximation for MAX-3-SAT.
1 Introduction
The paper develops a general positive-semidefinite-rank method for proving strong lower bounds on SDP formulations and relaxations. It shows that constant-degree sum-of-squares relaxations are optimal among polynomial-size SDP relaxations for Boolean CSPs, while explicit polytopes have super-polynomial psd rank.
- Spectrahedral lifts of polytopes: The paper proves strong lower bounds for general SDP formulations of the cut, TSP, and stable set polytopes.
- Semidefinite relaxations and constraint satisfaction: Polynomial-size SDP relaxations cannot achieve arbitrarily good approximations for many NP-hard CSPs, including better than 7/8 for MAX-3-SAT.
- Spectrahedral lifts of polytopes: The first super-polynomial psd-rank lower bounds for explicit polytopes are obtained through a general lower-bound method.
- Semidefinite relaxations and constraint satisfaction: Degree-O(1) sum-of-squares relaxations are optimal among polynomial-size SDP relaxations for Boolean CSP approximation.
- Semidefinite relaxations and constraint satisfaction: Theorem 1.6 transfers failure of degree-d sum-of-squares approximation to every function subspace of dimension at most α · (n/ log n)^(d/4).
- Spectrahedral lifts of polytopes: Positive-semidefinite rank exactly characterizes the minimum size of a psd lift through slack-matrix factorizations.
- Positive semidefinite rank and sum-of-squares degree: The refined argument yields a lower bound rkpsd(corrn) ⩾ 2^(Ω(n^δ)) for some δ > 0.
- Positive semidefinite rank and sum-of-squares degree: The framework links approximation lower bounds to psd-rank lower bounds through matrices associated with CSPs and sum-of-squares gaps.
2 Proof overview and setup
The proof overview connects psd-rank lower bounds to sum-of-squares degree through pseudo-densities, quantum learning, and low-degree approximations. The strategy constructs separating functionals and reduces high-degree factorizations using random restrictions.
- Conclusion: The combined argument converts low-degree sum-of-squares obstructions into lower bounds on psd rank.The construction first separates low-degree factorizations and then applies approximation and restriction arguments to general low-rank factorizations.
- Factorizations and separation: A pseudo-density yields a linear functional that separates the target matrix from matrices admitting low-degree psd factorizations.The separation follows from convex duality and the characterization of sum-of-squares degree through pseudo-densities.
- Setup: The paper studies Boolean functions, Fourier degree, density operators, psd factorizations, and pseudo-densities as the main ingredients of its lower-bound framework.A degree-d pseudo-density has unit expectation and nonnegative inner products with squares of functions of degree at most d/2.
- Quantum learning: Quantum learning approximates matrix-valued functions by squares of low-degree polynomial matrices with controlled error on selected tests.The degree bound depends on parameters including relative entropy, while the approximation is interpreted through matrix multiplicative weights or mirror descent.
- Degree reduction: Random restrictions reduce the degree of a learned approximator after fixing variables outside a randomly chosen small subset.The resulting partial polynomial is expected to have substantially smaller degree, at least approximately, enabling the degree-reduction step.
3 PSD rank and sum-of-squares degree
This section formalizes the bridge between pseudo-densities, low-degree psd factorizations, and psd-rank lower bounds. Scaling and degree-reduction theorems make the separating functional applicable to broader matrix factorizations.
- Functional setup: The functional L_D is nonnegative on matrices factored through squares of polynomials whose matrix-valued factor has degree at most d/2.This follows directly from the defining positivity condition of a degree-d pseudo-density.
- Proof strategy: The proof applies scaling, approximates a general factorization by a suitable low-degree one, and then invokes degree reduction to obtain the separating lower bound.The expectation and norm conventions used in this argument average over subsets S of fixed size and inputs x.
- Main lower bound: Theorem 3.1 quantitatively lower-bounds psd rank using a degree-d pseudo-density and a nonnegative matrix satisfying the theorem’s size conditions.The theorem is stated for n ≥ 2m and includes a universal constant in its bound.
- Degree reduction: Degree reduction shows that L_D remains approximately nonnegative when the factorization degree exceeds d/2 but is bounded by a controlled parameter.This theorem applies to factorizations N′(S,x)=Tr(A_S^2B_x) with bounded degree for the matrix-valued function x ↦ B_x.
- Scaling: The psd-factorization scaling theorem normalizes factors while preserving the matrix and controlling operator and trace norms.The construction starts from a factorization whose size is governed by psd rank and rescales its positive semidefinite factors.
S Tr PSQx
The technical argument proves that pseudo-density functionals stay nearly nonnegative on appropriately structured factorizations. It combines matrix factorization scaling, degree reduction, Fourier decomposition, and a psd-rank application to matrices derived from Boolean functions.
- Density-matrix approximation: The approximation argument replaces an arbitrary density matrix by a normalized square p(F)^2 of a low-degree polynomial in a symmetric matrix F.The degree depends on entropy, operator norms, and the approximation tolerance.
- Functional bound: The resulting factorization allows the pseudo-density functional to be bounded from below through expectations involving Tr(P_S p(F_x)^2).The proof uses the pseudo-density condition, norm bounds, and the degree of the polynomial approximation.
- Degree reduction: The degree-reduction theorem decomposes a matrix-valued factor into low- and high-degree parts on each subset S.Fourier supports of the two parts are disjoint, allowing their contributions to be controlled separately.
- Application to Boolean functions: For f with d + 2 = deg_sos(f), the constructed matrix M_f^n transfers sum-of-squares degree information into psd-rank lower bounds.The matrix admits an explicit psd factorization based on coefficient vectors and rank-one matrices indexed by monomials.
- Application to Boolean functions: If a degree-d pseudo-density correlates negatively with f by at least ε, the corresponding matrix inherits a quantitative psd-rank lower bound.The negative correlation gives a separating functional value, and the contrapositive of the main theorem yields the rank bound.
4 Approximations for density operators
The section develops entropy-based approximations for density operators against individual tests and convex families of tests. Its central result replaces a high-entropy state by the square of a low-degree polynomial in a test operator, with classical junta and function analogues.
- Overview: High-entropy density operators can be approximated by simple states when tested only with low-degree or otherwise restricted functionals.The section first treats a single test and then extends the principle to families of tests.
- Single-test approximation: For a symmetric matrix F and density matrix Q, a low-degree polynomial in F produces a density matrix whose test value approximates Tr(FQ).The polynomial degree is controlled by the operator norm, relative entropy to the uniform state, and ε.
- Single-test approximation: The construction first uses an entropy-regularized exponential state and then approximates the matrix exponential by a polynomial square.Univariate polynomial approximation to e^x transfers to approximation of e^F in trace norm.
- Families of tests: Against a compact convex family of tests, a density operator is approximated by p(F)^2 for some F in the family and a normalized low-degree polynomial p.The approximation is simultaneous with respect to the tests in the family.
- Sparse and classical approximations: Mirror descent yields sparse approximations using finitely many test functionals, with the number of terms controlled by relative entropy, tolerance, and test magnitude.The same framework has a classical analogue for nonnegative functions and probability measures.
- Sparse and classical approximations: For product spaces, nonnegative functions can be approximated by normalized juntas while preserving their tested behavior within the stated tolerance.The resulting junta size depends on the original test family and approximation parameters.
5 The correlation polytope
The section develops a positive-semidefinite-rank lower bound for the correlation polytope and transfers it to cut, TSP, and stable set polytopes. The proof uses pseudo-densities derived from Grigoriev’s polynomial-functional construction.
- Correlation-polytope connection: A nonnegative quadratic function on the Boolean cube yields a valid linear inequality for the correlation polytope.The associated matrix provides a slack-matrix connection used in the lower-bound argument.
- Transfer to other polytopes: The correlation polytope is linearly isomorphic to the cut polytope, and related faces of TSP and stable set polytopes project to it.These relationships transfer correlation-polytope lower bounds to the other polytopes.
- Pseudo-density construction: A degree-m pseudo-density represents Grigoriev’s linear functional on multilinear polynomials while preserving the required positivity conditions.The construction uses interpolation over Hamming weights and symmetry of the Boolean cube.
- Lower-bound mechanism: The resulting pseudo-density has controlled norm and produces a negative correlation with the relevant quadratic function.These bounds feed into the positive-semidefinite-rank lower-bound theorem.
- Lower-bound mechanism: The general method yields strong lower bounds on semidefinite formulations through positive semidefinite rank.The section’s result is applied to the correlation polytope and then transferred through the stated polytope relationships.
6 Optimality of low-degree sum-of-squares for max CSPs
This section characterizes semidefinite relaxations for max-CSPs through spectrahedra and positive semidefinite rank, then shows that polynomial-size general SDPs cannot outperform suitable low-degree sum-of-squares relaxations. Quantitative consequences include lower bounds for MAX-3-SAT.
- SDP formulation: Max-CSP SDP relaxations use an instance-independent spectrahedron and linearize each objective through matrix inner products.Assignments are mapped to positive semidefinite matrices whose inner products recover constraint values.
- Sum-of-squares formulation: The degree-d sum-of-squares relaxation has a spectrahedral representation based on a positive semidefinite moment matrix with consistency constraints.The matrix entries encode unions of index sets and normalize the empty-set entry to one.
- Rank characterization: The minimum size of an SDP achieving a given max-CSP approximation equals the positive semidefinite rank of an associated matrix.This reduces approximation lower bounds to positive-semidefinite-rank lower bounds.
- General SDPs versus SOS: General SDP relaxations for max-CSPs are no more powerful than low-degree sum-of-squares relaxations in the polynomial-size regime.The paper states this as its central comparison between arbitrary SDPs and the sum-of-squares hierarchy.
- General SDPs versus SOS: If degree-d sum-of-squares fails to achieve a (c+ε, s)-approximation, sufficiently small SDPs also fail to achieve a (c, s)-approximation at larger instance sizes.The quantitative theorem bounds SDP size by K n d(n)^2/8 and relates the larger size parameter to n^4d(n).
- MAX-3-SAT consequence: For MAX-3-SAT, known sum-of-squares lower bounds imply that polynomial-size SDP relaxations cannot achieve better than a 7/8-approximation.The construction can yield a lower bound of order N^Ω(log N / log log N) for the relevant positive semidefinite rank.
7 Nonnegative rank
The section relates nonnegative rank to junta degree through local pseudo-densities and applies this connection to explicit matrix lower bounds. It also derives consequences for correlation-type matrices and Unique Games.
- Junta degree and pseudo-densities: A nonnegative function has junta degree greater than d exactly when a d-local pseudo-density correlates negatively with it.This characterization converts junta-degree lower bounds into pseudo-density certificates.
- Nonnegative-rank method: The method approximates factors in a nonnegative factorization by low-degree juntas and uses pseudo-density correlations to lower bound nonnegative rank.The argument controls the number of relevant coordinates and combines the resulting estimates through inner products.
- Correlation-polytope application: For the correlation polytope, the method gives rk⁺(corr_n) ≥ 2^Ω(n^1/3), while the section notes this is weaker than a 2^Ω(n) bound.The weaker bound follows by choosing the parameter m appropriately in the preceding result.
- Explicit lower-bound example: A specially supported pseudo-density gives an approximate junta-degree lower bound for a Boolean function and extends to functions satisfying the same support condition.The support is restricted to strings of Hamming weight at most one.
- Explicit lower-bound example: The resulting nonnegative-rank lower bound applies to matrices containing a submatrix corresponding to the unique disjointness problem.This is stated as a generalization beyond one particular matrix construction.
- Unique Games application: The same relation between local pseudo-densities and nonnegative rank yields LP hardness consequences for Unique Games.The stated consequence concerns polynomial-size LP relaxations and a (1−δ, 1/q+δ)-approximation.