Boaz Barak: New 11 Week Seminar Series on the Sum of Squares Method

Repeats every week every Monday until Fri Dec 19 2014.
Monday, September 29, 2014 - 2:00pm to 5:00pm
Monday, October 6, 2014 - 2:00pm to 5:00pm
Monday, October 13, 2014 - 2:00pm to 5:00pm
Monday, October 20, 2014 - 2:00pm to 5:00pm
Monday, October 27, 2014 - 2:00pm to 5:00pm
Monday, November 3, 2014 - 2:00pm to 5:00pm
Monday, November 10, 2014 - 2:00pm to 5:00pm
Monday, November 17, 2014 - 2:00pm to 5:00pm
Monday, November 24, 2014 - 2:00pm to 5:00pm
Monday, December 1, 2014 - 2:00pm to 5:00pm
Monday, December 8, 2014 - 2:00pm to 5:00pm
Monday, December 15, 2014 - 2:00pm to 5:00pm
Location: 
32-G575
Speaker: 
Boaz Barak
Biography: 
Microsoft New England

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