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 _{  Semidefinite programs} _{  Degree 2 SoS SDP for MaxCut } 

30 Aug 
Sum of Squares SDP 

4 Sept 
Sum of Squares SDP _{  Sum of squares vs SheraliAdams LP} 

6 Sept 
Sum of Squares SDP _{  Finding a planted MaxCut } 

11 Sept 
_{  General sum of squares SDP } _{  SoS proof system } 

13 Sept 
Robust Mean Estimation via SOS 

18 Sept 
Robust Linear Regression 

20 Sept 
Learning Mixtures of Gaussians 

25 Sept 
Injective Tensor norm _{  certifying hypercontractivity of Gaussians } 

27 Sept 
Tensor PCA & Random 3XOR 

2 Oct 
Noisy Tensor Completion 

4 Oct 
Tensor Decomposition _{  SoS based algorithm for 3 tensors } 

9 Oct 
Tensor PCA via higher degree SoS 

11 Oct 
Random Matrices: Moment/Trace method 

16 Oct 
Random Projection Rounding _{  Maximizing psd forms Nesterov } _{  Graph Coloring  KargerMotwaniSudan} 

18 Oct 
Global correlation rounding: Max Bisection 

23 Oct 
Global correlation rounding: Low thresholdrank graphs 

25 Oct 
Degree 2 SoS SDP _{  Generic Rounding } _{  Integrality Gaps } 

30 Oct 
Optimality of Degree 2 SoS SDP _{  Dictatorship testing gadgets } _{  From Integrality Gaps to Dictatorship tests } 

1 Nov 
SoS lower bounds: Grigoriev's lower bound for 3XOR 

6 Nov 
SoS lower bounds: planted clique and pseudocalibration 

8 Nov 
Pseudocalibration and distinguishing polynomials 

13 Nov 
Flag Algebras 

15 Nov 
Solving SDPs via Ellipsoid Algorithm 

20 Nov 
Solving SDPs via Matrix Multiplicative Weights 

22 Nov 


27 Nov 

29 Nov 