The Sum of Squares Algorithm: applications, connections, and questions
The Sum of Squares (SoS) algorithm (Parrilo '00, Lasserre '01) is a semidefinite programming relaxation that has been proposed in various communities under varying names.
I'll give a survey of the algorithm from a theoretical computer science perspective, particularly focusing on recent connections to the unique games conjecture and the quantum separability problem.
Some of the topics I hope to cover are:
1) Definition of the primal and dual SoS program in terms of pseudoexpectations and the Positivstellensatz proof system.
2) Lower bounds for random 3XOR
3) A generic scheme for rounding SoS, with applications to the quantum separability problem.
4) Certifying hypercontractivity of low degree polynomials using SoS, with applications to the unique games conjecture.