For people on this list interested in Sum-of-Squares, Unique Games Conjecture, etc.. I will give a general-audience talk on the Sum of Squares method and its Theoretical Computer Science applications on Wednesday September 3rd 10-11:30am, as well as an 11-week seminar series on the topic on Mondays 2-5pm starting Sep 29th. (The talk and seminar series will be independent of one another, and neither one is required for following the other.) See titles and abstracts below, as well as the webpage  http://www.boazbarak.org/sos for more information.

----

TALK TITLE: Sum of Squares Proofs and the Quest towards Optimal Algorithms

TIME AND PLACE: Wednesday, Sep 3rd, 10:00am-11:30am, room 32-G449 Kiva

ABSTRACT:

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.

-----

SEMINAR SERIES TITLE: Sum of squares upper bounds, lower bounds, and open problems.

TIME AND PLACE: Mondays 2-5pm, starting Sep 29, 32-G575

WEBPAGE: http://www.boazbarak.org/sos

This mini-course/seminar series will cover recent results and research directions on the "Sum of Squares" (SOS) algorithm, and its applications 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 math 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 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 the course, please sign up for its mailing list, which can be found from the course webpage http://www.boazbarak.org/sos.