# Sum-of-squares proofs and the quest toward optimal algorithms

arXiv: https://arxiv.org/abs/1404.5236 · HTML: https://mlsanity.com/paper/1404.5236/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Apr 2014.

## Built on by (most cited first, 12 of 12)

- [Low-Degree Multicalibration](https://mlsanity.com/paper/2203.01255/) (2022)
- [Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation](https://mlsanity.com/paper/2211.00724/) (2022)
- [Are Graph Neural Networks Optimal Approximation Algorithms?](https://mlsanity.com/paper/2310.00526/) (2023)
- [AI Descartes: Combining Data and Theory for Derivable Scientific Discovery](https://mlsanity.com/paper/2109.01634/) (2021)
- [Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions](https://mlsanity.com/paper/2305.10227/) (2023)
- [Kalman Filtering with Adversarial Corruptions](https://mlsanity.com/paper/2111.06395/) (2021)
- [Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures](https://mlsanity.com/paper/2112.05445/) (2021)
- [Private graphon estimation via sum-of-squares](https://mlsanity.com/paper/2403.12213/) (2024)
- [Cryptographic Hardness of Score Estimation](https://mlsanity.com/paper/2404.03272/) (2024)
- [A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy](https://mlsanity.com/paper/2102.08019/) (2021)
- [Computational Lower Bounds for Regret Minimization in Normal-Form Games](https://mlsanity.com/paper/2411.01721/) (2024)
- [Algorithms with Polynomially-Improved Approximation Factors for the 2 rightarrow q Norm, and Applications](https://mlsanity.com/paper/2605.25303/) (2026)

## Abstract (arXiv)

In order to obtain the best-known guarantees, algorithms are traditionally tailored to the particular problem we want to solve. Two recent developments, the Unique Games Conjecture (UGC) and the Sum-of-Squares (SOS) method, surprisingly suggest that this tailoring is not necessary and that a single efficient algorithm could achieve best possible guarantees for a wide range of different problems. The Unique Games Conjecture (UGC) is a tantalizing conjecture in computational complexity, which, if true, will shed light on the complexity of a great many problems. In particular this conjecture predicts that a single concrete algorithm provides optimal guarantees among all efficient algorithms for a large class of computational problems. The Sum-of-Squares (SOS) method is a general approach for solving systems of polynomial constraints. This approach is studied in several scientific disciplines, including real algebraic geometry, proof complexity, control theory, and mathematical programming, and has found applications in fields as diverse as quantum information theory, formal verification, game theory and many others. We survey some connections that were recently uncovered between the Unique Games Conjecture and the Sum-of-Squares method. In particular, we discuss new tools to rigorously bound the running time of the SOS method for obtaining approximate solutions to hard optimization problems, and how these tools give the potential for the sum-of-squares method to provide new guarantees for many problems of interest, and possibly to even refute the UGC.