Sums of Squares upper bounds, lower bounds, and open questions

Boaz Barak

Mondays 2-5pm, Fall 2014 (First lecture September 29th), room 32-G575 (MIT Stata center)

See all lecture notes in a single pdf file, as well as abstract, slides and videos of (more or less) general-audience talks on this topic. You might also be interested in the videos of these talks by David Steurer at the Midrasha Mathematicae (see also this blog post): part 1 part 2 part 3 part 4

This mini-course/seminar series will cover recent results and research directions on the "Sum of Squares" (SOS) algorithm, and its application to theoretical computer science.

The "Sum of Squares" algorithm was independently discovered by researchers from several communities, including Shor, Nesterov, Parrilo, and Lasserre, and is an algorithmic extension of classical mmath results revolving around Hilbert's 17th question. It was recently proposed as a route to resolving central theoretical CS questions such as the truth of Khot's "Unique Games Conjecture".

In these lectures I will cover the SOS algorithm from a theoretical Computer Science perspective, with an emphasis on very recent results (including some not yet published..) showing its power and limitations, as well as on the many open questions in this area.

Despite describing the state of the art research, this course should be accessible to first year graduate students or advanced undergraduate students, as it requires no background except for "mathematical maturity" and comfort with basic linear algebra and probability theory. I will assume students are familiar with concepts such as eigenvalues and eigenvectors, norms and basic inequalities such as Cauchy-Schwarz/Holder, and probabilistic notions such as expectation/variance, tail bounds such as Chernoff, and the probabilistic method.

If you are interested in this seminar, please sign up for the seminar's mailing list. You may also want to come to my general audience talk on this topic on Wednesday September 3.

See also lecture notes for a shorter summer course I gave on this topic.

Homework and lectures:

See all lecture notes in a single pdf file As I make corrections to these lecture notes, I will do them only for this single pdf file and not the individual notes below. See also this blog post for the list of open problems which I will try to keep updating as I learn of new developments.