In theoretical computer science, the Sum-of-Squares (SoS) hierarchy is often viewed as the ultimate benchmark for polynomial-time algorithms. It provides a sequence of increasingly powerful semidefinite programming (SDP) relaxations for optimization and certification problems. If a problem cannot be solved by a high-degree SoS relaxation, it is widely believed to be computationally intractable for any efficient algorithm.
Understanding the fundamental limits of this hierarchy allows researchers to map out the boundaries of what is computationally possible, establishing unconditional lower bounds against a massive class of convex optimization algorithms.
The Core Mechanism: Tricking the Algorithm with Pseudo-Expectations
To understand why the SoS hierarchy fails on certain instances, we must look at how it represents solutions. For a polynomial optimization problem over variables $x_1, \dots, x_n$, a true probability distribution $\mathbb{E}$ over valid solutions must satisfy a basic property: the expected value of any squared polynomial must be non-negative, $\mathbb{E}[P(x)^2] \ge 0$.
The degree-$d$ SoS hierarchy relaxes this requirement. Instead of looking for a real probability distribution, it searches for a pseudo-expectation operator $\tilde{\mathbb{E}}$ that maps polynomials of degree at most $d$ to real numbers. This operator must satisfy:
- $\tilde{\mathbb{E}}[1] = 1$
- $\tilde{\mathbb{E}}[P(x)^2] \ge 0$ for all polynomials $P$ of degree at most $d/2$.
Proving an SoS lower bound means constructing a valid pseudo-expectation operator for an instance where no true solution exists, or where the true optimum is much worse than what $\tilde{\mathbb{E}}$ claims. If we can build such an operator and prove it is positive semidefinite (PSD), we have successfully "tricked" the SoS algorithm. The algorithm will look at the pseudo-expectation, see that all squares are non-negative, and conclude that a high-quality solution exists, failing to certify the true bounds of the problem.
The Planted Clique Problem and the Square-Root Barrier
A classic arena for testing the limits of SoS is the Planted Clique problem. Given a random graph $G(n, 1/2)$, the largest clique is typically of size $2\log n$. If we "plant" a clique of size $k$, can an algorithm find it or certify its absence?
Simple spectral methods can easily find a planted clique if $k \ge \sqrt{n}$. Breaking this $\sqrt{n}$ barrier has been a long-standing challenge. In Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique, Raghu Meka et al. demonstrated that powerful SDP techniques face fundamental limitations here, failing to break the square-root barrier.
Subsequently, in Sum-of-squares lower bounds for planted clique, Raghu Meka et al. proved the first average-case lower bound for constant-round SoS, showing that the hierarchy cannot find a planted clique or refute its existence when $k \ll \sqrt{n}$. This reinforced the belief that the $\sqrt{n}$ barrier is a fundamental computational limit rather than a limitation of simple algorithms.
Pairwise Independence as a Source of Hardness
Why do random problems fool such a powerful proof system? In Sum of Squares Lower Bounds from Pairwise Independence, Boaz Barak et al. provided an elegant structural answer: pairwise independence.
For many Constraint Satisfaction Problems (CSPs), if the problem's predicates possess a high degree of local independence, local consistency checks cannot detect global unsatisfiability. The authors showed that pairwise independence in random structures is sufficient to generate hard instances that fool the SoS hierarchy up to $\Omega(n)$ degree. This provided a general recipe for constructing hard instances without relying on complex, problem-specific predicates.
While many results focus on lower bounds, understanding what the hierarchy can prove is equally vital for establishing tight limits. For instance, in Majority is stablest: discrete and SoS, Anindya De et al. established a version of the "Majority is Stablest" theorem within the SoS framework, which helps clarify the exact boundary where integrality gaps can or cannot be refuted.
When Higher Degrees Fail: The Sherrington-Kirkpatrick Model
One might hope that increasing the degree of the SoS relaxation from degree 2 (basic SDP) to degree 4 or higher would yield substantially tighter bounds. However, recent work shows that for many disordered systems, higher-degree moments offer surprisingly little benefit.
A prime example is the Sherrington-Kirkpatrick (SK) Hamiltonian from statistical physics, which involves maximizing a quadratic form $x^T J x$ over the hypercube $x \in \{-1, 1\}^n$ for a random Gaussian matrix $J$. The basic spectral certificate (the top eigenvalue of $J$) gives an upper bound of $2\sqrt{n}$. However, the true maximum is known to be approximately $1.527\sqrt{n}$ (the Parisi value).
Can SoS close this gap? In A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian, Dmitriy Kunisky et al. proved a tight degree-4 SoS lower bound, demonstrating that degree-4 relaxations offer only a marginal improvement over the basic spectral certificate. To extend this to even higher degrees, in Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes, Mrinalkanti Ghosh et al. introduced a reduction via a problem called Planted Affine Planes (PAP). The authors showed that even high-degree SoS relaxations ($n^{\Omega(\epsilon)}$) fail to improve upon the trivial spectral bounds for certifying the SK Hamiltonian, illustrating a fundamental limitation in ruling out solutions near the spectral edge.
Pervasive Limits Across Optimization and Inference
The failure of SoS to beat simple baselines is a recurring pattern across diverse mathematical domains:
- Densest $k$-Subgraph: For finding a subgraph of size $k$ with maximum edge density, Aaron Potechin et al. showed in Sum-of-Squares Lower Bounds for Densest k-Subgraph that SoS cannot beat existing approximation limits in the sub-linear regime ($k \le \sqrt{n}$), matching the predictions of the log-density framework.
- Sparse Independent Set: In sparse random graphs, Aaron Potechin et al. demonstrated in Sum-of-Squares Lower Bounds for Sparse Independent Set that high-degree semidefinite programming hierarchies fail to improve upon the certification bounds provided by basic degree-2 relaxations.
- Non-Gaussian Component Analysis (NGCA): In statistical inference, Ilias Diakonikolas et al. established the first super-constant degree SoS lower bound for NGCA in Sum-of-squares lower bounds for Non-Gaussian Component Analysis, proving the existence of an information-computation gap where convex optimization cannot find a hidden non-Gaussian signal without excess data.
- Linear Systems ($k$-LIN): In cryptography and coding theory, understanding the hardness of refuting random linear equations is vital. In Spectral Refutations of Semirandom k-LIN over Larger Fields, Nicholas Kocurek et al. utilized the SoS hierarchy to establish tight lower bounds for refuting semirandom $k$-LIN instances over large finite fields.
The Physics Connection: Glassy Landscapes and Hard Regimes
To gain intuition on why these lower bounds occur, we can look to the physics of disordered systems. As explored by David Gamarnik et al. in Disordered Systems Insights on Computational Hardness, many average-case optimization problems exhibit a "glassy" free-energy landscape.
In these landscapes, valid configurations are shattered into numerous isolated clusters separated by high energy barriers. When an algorithm like SoS attempts to inspect the space via low-degree polynomials, it smooths out the local geometry but fails to capture the global topological constraints.
For instance, in The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime, Jess Banks et al. analyzed the Lovász $\vartheta$ function (a degree-2 SoS proof system) on random regular graphs, demonstrating that it fails to refute $k$-colorability even deep within the hard regime. The local structure of the graph looks perfectly colorable to any low-degree check, meaning the global contradictions can only be seen by looking at high-degree correlations that are computationally intractable to evaluate.
Ultimately, the study of SoS lower bounds reveals that for a wide class of random and planted problems, the geometry of the problem space itself creates an insurmountable barrier. No matter how many higher-order moments are thrown at the problem, pseudo-expectation operators can be constructed to mimic valid solutions, defining the true limits of algorithmic certification.
Key Foundational Work
Sum of Squares Lower Bounds from Pairwise Independence (2015) — contributed 4 concept elements to this direction.
Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique (2013) — contributed 3 concept elements to this direction.
Sum-of-squares lower bounds for planted clique (2015) — contributed 1 concept elements to this direction.