CMU 15-859GG
Proofs vs Algorithms: The Sum-of-Squares Method

Instructor: Pravesh K. Kothari (Gates 7105)
TA: Peter Manohar (Gates 9007)


Course Summary

Syllabus: Welcome to 15-859-GG! This seminar examines the sum-of-squares method with an emphasis on recent developments and open directions for research. We will cover use of this method in designing algorithms for both worst-case optimization problems such as Max-Cut and Coloring and average-case problems arising in machine learning and algorithmic statistics such as learning mixtures of Gaussians and robust statistics. We will also cover techniques for proving lower-bounds on this method and its connection to restricted algorithmic frameworks such as Statistical Query Model, the Low-Degree Likelihood Ratio Method and Extended Formulations.

Prerequisites: We will assume “mathematical maturity” and familiarity with topics that are typically covered in basic classes such as: eigen- vectors and eigenvalues, linear programming, LP duality and Farkas lemma, outline of ellipsoid method, basics of probability (expectation, variance, tail bounds), basic spectral graph theory (graphs and their adjacency matrices, relation between spectrum of adjacency matrix and random walk). Most of these ideas are covered in classes such as Theorist's Toolkit. Graduate level classes in Complexity Theory and Algorithm Design will help appreciate the content better.

Course Policies Please see Course Policies for other details on tentative syllabus, evaluation and getting help.


Administrative Information

Lectures: Tuesday 4:00 pm - 6:50 pm.
Zoom link on Diderot. First meeting: Sep 1
Listeners and Auditors are welcome. (Email Peter for zoom link).

Office Hours: Pravesh: Wed 3-4pm, Peter: Mon 2-3pm, also by appointment.

Diderot: Use Diderot to access interactive lecture notes, discussions and announcements.

Evaluation: 1. 4-6 homeworks (60 percent) - must be typeset and submitted every Tuesday (except HW0) through Gradescope
2. Expository Lecture Notes (40 percent, done individually) - on a related topic not covered in lectures. Details forthcoming.

Gradescope Sign up here (use your andrew ID to login please, and code MW86ZP if needed.)

Resources : Lecture notes and other references on Diderot.
A recent survey covering a subset of topics.

Related Classes : SoS Seminar at Princeton/MIT
Moses Charikar's Class on Hierarchies at Stanford
Luca Trevisan's Spectral Methods at Berkeley

Tentative Schedule
Lecture # Topic Notes Homework
1. 09/01 Introduction + Basics: Sum-of-Squares Proofs, Pseudo-distributions, Duality HW0 released (due 9/4)
2. 09/08 Sum-of-Squares Algorithm and Application to Max-Cut HW1 released (due 9/22)
3. 09/15 Quadratic Optimization over the Hypercube
4. 09/22 Approximating Graph Expansion HW1 due, HW2 released (due 10/06)
5. 09/29 Unique Games Conjecture and Connections
6. 10/06 Global Correlation Rounding
7. 10/13 Sum-of-Squares Lower Bounds: Grigoriev's Theorem
8. 10/20 Constrained SoS and Refuting Random CSPs
9. 10/27 Average-Case Algorithm Design via SoS: Clustering Spherical Mixtures
10. 11/10 Outlier-Robust Mean Estimation via Sum-of-Squares
11. 11/17 Tensor Decomposition via SoS
12. 11/24 List-decoding noisy linear equations
13. 12/01 SoS vs Spectral Algorithms
14. 12/08 Sum-of-Squares vs Low-degree Polynomials