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:** By appointment.

**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. Weight for your final grade will be split: 50% psets, 50% course project.

**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
- An iteration of this course from two years ago

No. | Date | Topics | Notes/References |
---|---|---|---|

1 | 9/5 | Linear proofs and quadratic proofs | |

2 | |||

3 | |||

4 | |||

5 | |||

6 | |||

7 | |||

8 | |||

9 | |||

10 | |||

11 |

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.

- 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.