SoS Meta-Theorem

The SoS meta-theorem, established by Barak, Hopkins, Kelner, Kothari, Moitra, and Potechin (2019), is a foundational result in theoretical computer science that establishes the sum-of-squares (SOS) hierarchy as a "universal algorithmic framework" for a broad class of computational problems. The theorem shows that for many problems of interest — including planted clique, sparse PCA, community detection, and tensor decomposition — if the SOS hierarchy at constant degree cannot solve the problem, then no algorithm from a large and natural class of efficient methods can solve it either.

The meta-theorem transforms the SOS hierarchy from a specific algorithmic technique into a kind of "computational thermometer: