View source for 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 Hierarchy|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: