Sum-of-Squares Hierarchy

The sum-of-squares (SOS) hierarchy is a systematic method for solving polynomial optimization problems through a sequence of increasingly tight semidefinite programming relaxations. Introduced independently by Jean-Bernard Lasserre and Pablo Parrilo in the early 2000s, the hierarchy provides a powerful framework for both proving lower bounds on the difficulty of computational problems and for constructing efficient approximation algorithms. At each level k, the SOS relaxation considers degree-2k sum-of-squares proofs; as k increases, the relaxation becomes tighter but computationally more expensive. The hierarchy occupies a unique position in computational mathematics: it is simultaneously a constructive algorithm, a proof system, and a lens through which the structure of hard problems becomes visible.

The Basic Idea

A polynomial is a sum of squares if it can be written as a sum of squared polynomials: f(x) = g₁(x)² + g₂(x)² + ... + gₘ(x)². Every sum-of-squares polynomial is non-negative everywhere, and for univariate polynomials the converse is also true: every non-negative polynomial is a sum of squares. In multiple variables, this equivalence fails — there exist non-negative polynomials that are not sums of squares — but the gap between non-negativity and sum-of-squares is precisely what makes the hierarchy interesting.

The SOS hierarchy approaches a polynomial optimization problem — minimize f(x) subject to polynomial constraints gᵢ(x) ≥ 0 — by replacing the intractable search over all non-negative polynomials with a tractable search over sum-of-squares polynomials of bounded degree. At level k, the relaxation asks: can we write f(x) - λ as a sum of squares multiplied by the constraints, using polynomials of degree at most 2k? If yes, then λ is a lower bound on the true minimum. As k increases, the bounds become tighter, and in the limit k → ∞, the bounds converge to the true minimum.

Semidefinite Programming and Computational Cost

The key mathematical fact that makes the SOS hierarchy computationally tractable is that checking whether a polynomial is a sum of squares is equivalent to checking whether a certain matrix is positive semidefinite — a problem that can be solved in polynomial time using semidefinite programming. At level k, the matrix has size roughly n^k × n^k, where n is the number of variables. This means that:

• Level 1 (degree-2 proofs) corresponds to linear programming and is solvable in polynomial time.
• Level 2 (degree-4 proofs) corresponds to semidefinite programming over n² × n² matrices and is still polynomial-time but with a significant practical cost.
• Level k requires time n^O(k), which is polynomial for constant k but becomes super-polynomial as k grows with n.

The hierarchy thus interpolates between tractable and intractable: low levels are efficient but loose; high levels are tight but expensive. The computational phase transition — the level at which the relaxation becomes exact — is a central object of study.

The SOS Hierarchy and the Statistical-Computational Gap

The SOS hierarchy occupies a central position in the theory of the statistical-computational gap. For many problems where efficient algorithms are unknown — including planted clique, sparse PCA, and tensor decomposition — the SOS hierarchy at constant degree captures the best known polynomial-time algorithms. The SoS meta-theorem of Barak et al. (2019) establishes that for a broad class of problems, if the SOS hierarchy at level O(1) fails to solve a problem, then no polynomial-time algorithm from a large class (including spectral methods, local algorithms, and convex relaxations) can solve it either.

Conversely, lower bounds against low-degree SOS proofs provide strong evidence that a problem is computationally hard, even when it is statistically easy. The proof strategy is elegant: one shows that for random instances, no low-degree polynomial can distinguish the planted structure from pure noise. Since the SOS hierarchy produces only low-degree certificates, this implies that the hierarchy cannot certify the absence of a solution, and hence cannot solve the problem. The hierarchy thus serves as a kind of "universal algorithmic lens": if a problem cannot be solved by low-degree SOS, it likely cannot be solved by any known efficient method.

This connection makes SOS lower bounds a crucial tool for understanding the limits of machine learning and average-case complexity. The recent discovery that the SOS hierarchy can solve the sum-of-squares certificate problem for certain tensor decomposition tasks — tasks previously thought to require exponential time — illustrates both the power and the subtlety of the framework.

Proof Complexity and the Hierarchy as a Proof System

The SOS hierarchy is not merely an algorithm. It is a proof system — a formal system for establishing the non-existence of solutions to constraint satisfaction problems. In this guise, it connects to the broader field of proof complexity, which studies the minimum size of proofs in various logical systems.

The SOS proof system is remarkably powerful. It subsumes many other proof systems, including the Nullstellensatz and polynomial calculus systems. A lower bound in the SOS system therefore implies lower bounds in these weaker systems. The hierarchy also connects to Sherali-Adams hierarchies — a related family of linear programming relaxations — through a precise relationship: the SOS hierarchy at level k is at least as powerful as Sherali-Adams at level 2k.

The proof-complexity perspective reveals something deeper: the SOS hierarchy is a formalization of what it means to "prove" that a problem is hard. The degree of the proof corresponds to the amount of local information that must be combined to establish global impossibility. Problems with low-degree SOS lower bounds are problems where local consistency does not imply global consistency — a condition that is also characteristic of spin glasses and other disordered systems in statistical physics.

Applications and Frontiers

Beyond the statistical-computational gap, the SOS hierarchy has found applications across theoretical computer science:

Approximation algorithms: The Goemans-Williamson algorithm for MAX-CUT, which achieves the best-known approximation ratio of 0.878, is equivalent to the SOS hierarchy at level 1. Higher levels of the hierarchy have been used to obtain improved approximations for constraint satisfaction problems, though the gains diminish rapidly.

Quantum information: The SOS hierarchy provides upper bounds on quantum correlation values in Bell inequality experiments. The NPA hierarchy (Navascués-Pironio-Acín), which bounds quantum correlations, is a variant of the SOS hierarchy specialized to the quantum setting.

Control theory: SOS methods are used to certify stability of dynamical systems by finding Lyapunov functions — functions that decrease along trajectories and hence prove convergence. The search for polynomial Lyapunov functions is naturally formulated as an SOS program.

Robotics and motion planning: SOS programming has been used to plan collision-free trajectories and to verify the safety of control policies. The ability to handle non-convex constraints through convex relaxation makes SOS methods particularly attractive for safety-critical applications.

Open Problems

• The degree-exactness threshold. For which problems does the SOS hierarchy become exact at constant degree? For MAX-CUT, level 1 is not exact; for certain tensor problems, level 4 is. What determines the threshold?
• The integrality gap. How large can the gap be between the SOS relaxation and the true optimum? Recent results show that for some problems, the gap persists even at super-constant degree.
• The physics connection. The SOS hierarchy at level k is formally related to the k-th moment of the Gibbs measure in statistical physics. Can methods from spin glass theory (replica symmetry breaking, cavity method) be used to predict SOS performance?
• Practical scalability. Despite its theoretical power, the SOS hierarchy remains computationally expensive for large problems. Can problem-specific structure be exploited to reduce the degree requirements?

The sum-of-squares hierarchy is often presented as a technical tool for solving polynomial optimization problems. This is like presenting the telescope as a device for making distant objects appear closer — true, but missing the epistemological revolution. The SOS hierarchy is the computational equivalent of the renormalization group: it tells us which features of a problem matter at which scales of analysis. A degree-2 proof sees only pairwise interactions; a degree-4 proof sees quartic correlations; and the point at which the hierarchy becomes exact is the point at which the problem's true computational structure is revealed. The hierarchy does not just solve problems. It diagnoses them.