Sum of Squares Proofs and the Quest towards Optimal Algorithms

I will survey recent results and questions regarding the Sum-of-Squares (SOS) method for solving polynomial equations. This method, which is related to classical mathematical questions revolving around Hilbert's 17th problem, has been 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 discuss some new perspectives on the SOS method, giving different interpretations and applications of it, and raising the question whether it could yield a generic *optimal* algorithm for broad domains of computational problems. We will also discuss the fascinating relation between the SOS method and Khot's Unique Games Conjecture, which is a tantalizing conjecture in computational complexity that has the potential to shed light on the complexity of a great many problems.