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:
| 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 | notes |
| 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!)
Problem Set 1 – tentatively due Oct. 14
Problem Set 2 – due Nov. 23
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.
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!)
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.
Learning Gaussian Mixtures (some overlapping papers) paper 1 paper 2 paper 3 paper 4 (you don’t have to read all of them)
Online regression & bandits: Chen-Koehler-Moitra-Yau
Robust stochastic block model recovery: Ding-d’Orsi-Nasser-Steurer
Exact tensor completion: Potechin-Steurer
Best separable state: Barak-Kothari-Steurer
SDP size lower bounds via SoS: Lee-Raghavendra-Steurer
Mean-field approximation in Ising models: Jain-Koehler-Risteski
Turan problems (combinatorics): Raymond-Singh-Thomas
topics related to SDPs from Luca Trevisan’s beyond worst case analysis class: notes
LP extension complexity: Chen-Lee-Raghavendra-Steurer, Rothvoss
Approximation algorithms for scheduling: Levey-Rothvoss Davies-Kulkarni-Rothvoss-Tarnawski-Zhang
SoS + unique games conjecture: (many possible refs; ask me)
Faster tensor decomposition: Schramm-Steurer
Random 2CSPs: Deshpande-Montanari-O’Donnell-Schramm-Sen Musipatla-O’Donnell-Schramm-Wu
Quantum Max Cut: Anshu-Gosset-Morenz (other papers as well; ask me or Google)
(robust) sparse mean estimation: Diakonikolas-Kane-Karmalkar-Pensia-Pittas
Ideal Membership Problem: Bulatov-Rafiey
(Of course this is only a partial list – I just ran out of steam here!)