Sum of Squares Proofs and the Quest towards Optimal Algorithms

Wednesday, September 3, 2014 - 10:00am
Light Refreshments
G449 (Patil/Kiva)
Boaz Barak, Senior Researcher, Microsoft Research New England
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. 
The talk will be accessible for a general mathematically-mature audience, and assume no background on the SOS method or the unique games conjecture. It is partially based on joint works with Jonathan Kelner and David Steurer. If your interest is piqued by the talk, I will also give a 11 week seminar series on this topic on Mondays 2pm-5pm starting September 29th.