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 notes
4 Oct. 7 beyond the hypercube, robust mean estimation Barak Steurer notes Schramm notes
5 Oct. 14 clustering mixture models scribe notes Sam’s old notes Schramm notes video
6 Oct. 21 tensor decomposition notes Schramm notes video
7 Oct. 28 lower bounds 1: CSPs Barak-Steurer, sections 3.1 and 3.2. video (no audio)
8 Nov. 4 lower bounds 2: planted clique
9 Nov. 18 fast algorithms 1: spectral methods
10 Dec. 2 fast algorithms 2: matrix multiplicative weights
11 Dec. 9 differential privacy? best separable state? extension complexity?

(Many lecture topics are tentative!)

Assignments

Problem Set 1tentatively due Oct. 14

Problem Set 2 – due Nov. 23

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 the end of October. 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.

This list has a strong bias towards TCS and statistics, because that’s my area of expertise. However, other areas related to SoS or with SoS applications are also good fodder for projects – control theory, quantum information, etc.

(Of course this is only a partial list – I just ran out of steam here!)