Instructor: Prasad Raghavendra (Room: Soda 623)
Lectures: Tuesday & Thursday, 11:00am12:30pm @ Soda 320.
Office hours: Tuesday 1:302:30pm.
Piazza site: piazza.com/berkeley/fall2018/cs294
Prerequisites: Sound knowledge of basic algorithms, linear algebra and probability.
Evaluation criteria: The course will have a very short homework on most weeks of the semester, which will be selfgraded in class. Students will be required to act as scribes for the lectures. The breakdown is 40% homeworks, 35% scribing, 25% participation.
Sum of squares semidefinite program (SoS SDP) is a broadly applicable and powerful algorithmic tool.
Polynomial systems (systems of equalities and inequalities in many variables) are clearly a very rich and powerful language to express computational problems from a plethora of contexts including combinatorial optimization and machine learning. Specifically, a vast range of computational problems can be posed as solving or reasoning about polynomial systems over reals.
The sum of squares SDP (SOS SDP) are a hierarchy of algorithms to reason about systems of polynomial inequalities & equalities in many variables. Given the ubiquity of polynomial systems, it is clear that SoS SDP might be applicable in a variety of contexts. Surprisingly, the SoS SDP is not only applicable, it also yields the optimal/ best known algorithm in a wide range of settings!
While the underpinnings of sum of squares algorithm lie in classic work in real algebraic geometry and convex optimization, through its applications and the questions it poses, the work in this area has deep links to hardness of approximation, PCPs, highdimensional geometry, random matrices, quantum information and so on.
This is an advanced graduate class which starting with the basics of SoS SDPs, aims to broadly cover many of the very recent developments in SoS SDP based algorithms and corresponding lower bound results. A tentative list of topics planned for the course include:
Date  Lecture & Notes  Resources 

23 Aug 
Introduction 
Chapter I in BarakSteurer notes 
28 Aug 
Introduction to Semidefinite programming 
Notes on MaxCut SDP 
30 Aug 
Sum of Squares SDP 

4 Sept 
Sum of Squares SDP 

6 Sept 
Sum of Squares SDP 

11 Sept 
_{  General sum of squares SDP } 

13 Sept 
Robust Mean Estimation via SoS 

18 Sept 
Learning Gaussian Mixture Models 

20 Sept 
Robust Linear Regression 

25 Sept 

27 Sept 

2 Oct 

4 Oct 

9 Oct 

11 Oct 

16 Oct 

18 Oct 

23 Oct 

25 Oct 

30 Oct 

1 Nov 

6 Nov 

8 Nov 

13 Nov 

15 Nov 

20 Nov 

22 Nov 


27 Nov 

29 Nov 