This mini-course/seminar series will cover recent results and research directions on the "Sum of Squares" (SOS) algorithm, and its application to 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 math results revolving around Hilbert's 17th question. It was recently proposed as a route to resolving central Theoretical Computer Science questions such as the truth of Khot's "Unique Games Conjecture".
In these lectures I will cover the SOS algorithm from a Theoretical CS 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 state of the art research, this course requires fairly little mathematical background and should be accessible to first year graduate or advanced undergraduate students. If you are interested in this seminar series, please visit the website and sign up for the mailing list for more information.
Website: http://www.boazbarak.org/sos