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.

Syllabus

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:


Lectures

Date Lecture & Notes Resources

23 Aug

Introduction
- 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

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

 Holiday

27 Nov

29 Nov

Resources