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 by Parrilo and Lasserre in the early 2000s, the hierarchy provides a powerful framework for proving lower bounds on the difficulty of computational problems by certifying that no low-degree polynomial can distinguish random instances from structured ones. 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 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. Conversely, lower bounds against low-degree SOS proofs provide strong evidence that a problem is computationally hard, even when it is statistically easy. 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.