View source for 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|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|machine learning]] and [[Average-Case Complexity|average-case complexity]].

[[Category:Mathematics]] [[Category:Computer Science]] [[Category:Systems]]