The Sum of Squares Method (MIT 6.S977), Fall ’24

In this course we will study of algorithms and computational complexity through the lens of the Sum of Squares method (SoS), a powerful approach to algorithm design generalizing linear programming and spectral methods. We will choose some specific sub-topics based on student input, potentially including algorithms for combinatorial and continuous optimization (graphs, constraint satisfaction problems, unique games conjecture), applications to high-dimensional algorithmic statistics (robustness, privacy, method of moments), applications to quantum information, and an SoS perspective on computational complexity (of NP-hard problems and/or of statistical inference).

Prerequisites: Mathematical maturity is the main prerequisite. Familiarity with linear algebra, probability, discrete math, and algorithms at the advanced undergraduate level will be assumed.

Meeting time: Tuesdays and Thursdays, 9:30am – 11:00am

Location: 3-442

Instructor: Sam Hopkins

Office Hours: Tuesdays, 11:15am – 12:15pm, 32-G666.

Evaluation: Students will be expected to complete several problem sets and a research-oriented course project, which may consist of original research (theoretical and/or experimental!) and/or an exposition of 1 or 2 recent research papers. In addition, students will provide peer reviews for each others’ problem set solutions and course projects. Weight for your final grade will be split: 40% psets, 20% peer reviews, 40% course project.

Instructions for peer review.

Collaboration policy: You may collaborate with your peers on your problem sets in the following manner. You can have meetings to discuss and solve problems. At the end of a meeting, all records from the meeting must be destroyed. (No written notes, no whiteboard/chalkboard photos, etc.) Then, you must write your solutions on your own.

The course project can be done in groups of \(2\).

Collaborating with Google and AI Chatbots: While doing psets, you can ask Google/ChatGPT/Claude/Llama/etc questions about background material but not detailed questions about a particular problem. This will be policed on the honor system, i.e. not at all.

Example question which is within bounds: What is the expected value of \(\exp(-g^2 t^2)\) when \(g\) is a standard Gaussian?

Example question which is out of bounds: How do I prove that pinning reduces global correlation?

Resources: Some of the material in this course has been covered in other excellent courses and books. Here is a partial list:

Lectures + Lecture Notes

No. Date Topics Notes/References
1 9/5 Linear proofs and quadratic proofs lecture notes
2 9/10 Pseudoexpectations lecture notes
3 9/12 Gaussian rounding Barak-Steurer notes
4 9/17 Ellipsoid algorithm and other quadratic programming Barak-Steurer notes, Charikar-Wirth on Max-Cut Gain, Shmoys-Williamson book for PSD quadratic programming, lecture notes for ellipsoid
5 9/19 SoS over general domains, and beyond quadratics Barak-Steurer notes
6 9/24 Dense CSPs, Part 1 lecture notes (work in progress)
7 9/26 Dense CSPs, Part 2 lecture notes (work in progress)
8 10/1 Complexity of CSPs Barak-Steurer, chapter 3
9 10/3 Random CSPs, Part 1 scribe notes from 2022
10 10/8 Random CSPs, Part 2
11 10/10 Robust mean estimation Schramm notes
12 10/17 Robust mean estimation, continued Schramm notes
13 10/22 Robust regression Schramm notes
14 10/24 Mixture models Schramm notes Hopkins notes
15 10/29 Certifiable moments original paper
16 10/31 Tensor decomposition, Part 1 old video
17 11/5 Tensor decomposition, Part 2 notes Schramm notes
18 11/7 Tensor decomposition, Part 3? notes Schramm notes
19 11/12 Planted Clique I TBA
20 11/14 Planted Clique II TBA
21 11/19 Low-degree lower bounds Sidhanth’s notes
22 11/21 Mixture models, revisited (Allen Liu) TBA
23 11/26 Best separable state I TBA
24 12/3 Best separable state II TBA
25 12/5 Project presentations TBA
26 12/10 Project presentations TBA

Assignments