Fall 2018 CS 294: Sums of squares

Instructor: Prasad Raghavendra (Room: Soda 623)
Lectures: Tuesday & Thursday, 11:00am-12:30pm @ Soda 320.
Office hours: Tuesday 1:30-2: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 self-graded in class. Students will be required to act as scribes for the lectures. The breakdown is 40% homeworks, 35% scribing, 25% participation.

Course Description

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, high-dimensional 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

- history of sum of squares proofs

Chapter I in Barak-Steurer notes
Sum-of-squares introduction by Amir Ali Ahmadi

28 Aug

Introduction to Semidefinite programming
- Semidefinite matrices

- Semidefinite programs

- Degree 2 SoS SDP for MaxCut

Notes on MaxCut SDP

Blog post: Introduction to SoS hierarchy by Tselil Schramm

30 Aug

Sum of Squares SDP
- Pseudoexpectations/pseudomoments
- Duality of sum-of-squares proofs and pseudoexpectations

Chapter II in Barak-Steurer notes
Notes on SDP Duality

4 Sept

Sum of Squares SDP
- Strong duality in sum-of-squares SDPs

- Sum of squares vs Sherali-Adams LP

6 Sept

Sum of Squares SDP
- PTAS for MaxCut on bounded degree planar graphs

- 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

(Talk by Kothari)

25 Sept

Injective Tensor norm
- Moment tensors, hypercontractivity

- certifying hypercontractivity of Gaussians

27 Sept

Tensor PCA & Random 3-XOR

Section 6.1, 6.3 in Hopkins Phd. Thesis

2 Oct

Noisy Tensor Completion


4 Oct

Tensor Decomposition
- Jenrich's algorithm

- SoS based algorithm for 3 tensors

9 Oct

Tensor PCA via higher degree SoS

R-Rao-Schramm Bhattiprolu-Guruswami-Lee

11 Oct

Random Matrices: Moment/Trace method

16 Oct

Random Projection Rounding
- Goemans-Williamson algo for MaxCut

- Maximizing psd forms -Nesterov

- Graph Coloring - Karger-Motwani-Sudan

18 Oct

Global correlation rounding: Max Bisection

23 Oct

Global correlation rounding: Low threshold-rank graphs

25 Oct

Degree 2 SoS SDP
- Basic SDP for CSPs

- Generic Rounding

- Integrality Gaps

30 Oct

Optimality of Degree 2 SoS SDP
- Unique Games Conjecture and SSE

- Dictatorship testing gadgets

- From Integrality Gaps to Dictatorship tests

1 Nov

SoS lower bounds: Grigoriev's lower bound for 3-XOR

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