*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.

*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.

- homework 0 - prework
- September 29 - Lecture 1 - introduction
- October 6 - Lecture 2 -Max Cut, Sparsest Cut, Small Set Expansion and some relations of Isoperimetry and Hypercontractivity
- October 13 - Columbus day - no lecture?
- October 20 - FOCS 2014 - no lecture
- October 27 - Lecture 3 - SOS Lower Bounds: 3XOR/3SAT and Planted Clique
- November 3 - Lecture 4 - SOS Upper bounds: Planted sparse vector and dictionary learning
- November 10 - Veterans day - no lecture?
- November 17 - Sparsest cut and the ARV algorithm - guest lecture by Jon Kelner. (See lecture notes from my lecture on this topic in the summer course, as well as the draft of updated version scribed by Tal Wagner.)
- November 24 Lecture 6 - The SOS approach to refuting the Unique Games Conjecture.
- December 1 - Extension complexity - guest lecture by Ankur Moitra.
- December 8 - Lecture 8 - Semidefinite programming extension complexity and Open Problems.