Sum of Squares Proofs and the Quest towards Optimal Algorithms

Boaz Barak

Slides: PowerPoint Show format. See also slides from an earlier talk at ICM 2014 (see video), as well as slides and video for a less-technical general-audience talk at Harvard University. For fuller details, please see the lecture notes of my seminar series (where I also linked to a four-part lecture series by David Steurer).

Date: Wednesday, September 03, 2014
Time: 10:00 AM to 11:30 AM
Refreshments Time: 10:00 AM
Location: MIT, Stata center - G449 Kiva

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.