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:

- A book-in-progress by Barak and Steurer
- A course by Tselil Schramm on SoS and statistics
- A book by Fleming, Kothari, and Pitassi
- Course videos by Kothari

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!)

Problem Set 1 – tentatively due Oct. 14

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

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.

- Formulate a research question related to the course (and possibly also related to your main area of research) and investigate it.
- Read one or more papers from the SoS literature and write an exposition of them at a level understandable by the students of 6.S977. Optionally, extend one or more of the result in these papers.
- Implement one or more algorithms from the SoS literature and study their performance empirically.
- Combinations of any of the above.

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.