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

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: Fridays, 9:30am – 12:30am.

Location: 66-144 1-150 3-333

Instructor: Sam Hopkins

Office Hours: By appointment.

Piazza: We will use Piazza for course discussions. Please sign up here.

Evaluation: Students will be expected to complete two 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. Tentatively, weight for your final grade will be split as follows: 25% pset 1, 25% pset 2, 50% course project.

Sick/Absence Policy and Lecture Recordings: I will make a best effort to provide lecture recordings, using the lightweight lecture capture system in the room. If the capture system fails we will be out of luck. I will also provide links to resources which cover the material in each lecture (either external sources or lecture notes).

Feedback: Please offer any anonymous feedback you’d like to here. Non-anonymous feedback can be emailed to me.

Choosing topics: I have chosen tentative topics for all the lectures. However, there is flexibility in 2-3 lectures of the course. If there is a topic you’re excited to learn about which does not appear on the list of lecture topics, let me know. Maybe we can do something about it.

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 Sept. 9 optimization on the hypercube, max-cut sections 1.1, 1.2, and 2.1 of Barak-Steurer
2 Sept. 16 global correlation rounding notes Raghavendra notes on hyperfinite graphs slides video
3 Sept. 30 refuting random CSPs
4 Oct. 7 beyond the hypercube, robust mean estimation
5 Oct. 14 clustering mixture models
6 Oct. 21 tensor decomposition
7 Oct. 28 differential privacy
8 Nov. 4 fast algorithms 1: spectral methods
9 Nov. 18 fast algorithms 2: matrix multiplicative weights
10 Dec. 2 lower bounds 1: CSPs
11 Dec. 9 lower bounds 2: planted clique

(Many lecture topics are tentative!)

Assignments

Problem Set 1 – tentatively due Oct. 14

Problem Set 2 (not yet posted) – tentatively due Nov. 4

Course project – tentatively due December 14

The course project is an opportunity for you to dive deeper into the SoS research literature, make connections to your own research, and more! There is a great deal of flexibility in choosing your project. However, I need to approve all the project topics before you embark on them! I expect you to schedule a discussion of your project with me before Thanksgiving. You may (but are not required to!) work with a partner on your project.

Possible approaches to the project:

None of these options are preferred above others – in particular, original research is not a requirement for a successful project. (That said, it does of course carry many potential rewards – it is not uncommon for MIT course projects to end up as published papers!)

Deliverables:

You should produce a written report on your project activities. For expository projects, this report is your exposition. For research projects, this document should discuss the research problem you decided to investigate, why it merits your attention, how it relates to the subject of the course, and your findings.

Reports may vary in length, but when grading, I promise to read the first 10 pages of your report (typeset in a reasonable font with reasonable margins). I will read further material at my discretion.