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:** Tuesdays, 11:15am – 12:15pm, 32-G666.

**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. In addition, students will provide peer reviews for each others’ problem set solutions and course projects. Weight for your final grade will be split: 40% psets, 20% peer reviews, 40% course project.

Instructions for peer review.

**Collaboration policy:** You may collaborate with your peers on your problem sets in the following manner. You can have meetings to discuss and solve problems. At the end of a meeting, all records from the meeting must be destroyed. (No written notes, no whiteboard/chalkboard photos, etc.) Then, you must write your solutions on your own.

The course project can be done in groups of \(2\).

**Collaborating with Google and AI Chatbots:** While doing psets, you can ask Google/ChatGPT/Claude/Llama/etc questions about background material but not detailed questions about a particular problem. This will be policed on the honor system, i.e. not at all.

Example question which is within bounds: *What is the expected value of \(\exp(-g^2 t^2)\) when \(g\) is a standard Gaussian?*

Example question which is out of bounds: *How do I prove that pinning reduces global correlation?*

**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 | lecture notes |

2 | 9/10 | Pseudoexpectations | lecture notes |

3 | 9/12 | Gaussian rounding | Barak-Steurer notes |

4 | 9/17 | Ellipsoid algorithm and other quadratic programming | Barak-Steurer notes, Charikar-Wirth on Max-Cut Gain, Shmoys-Williamson book for PSD quadratic programming, lecture notes for ellipsoid |

5 | 9/19 | SoS over general domains, and beyond quadratics | Barak-Steurer notes |

6 | 9/24 | Dense CSPs, Part 1 | lecture notes (work in progress) |

7 | 9/26 | Dense CSPs, Part 2 | lecture notes (work in progress) |

8 | 10/1 | Complexity of CSPs | Barak-Steurer, chapter 3 |

9 | 10/3 | ||

10 | 10/8 | ||

11 | 10/10 | ||

12 | 10/17 | ||

13 | 10/22 | ||

14 | 10/24 | ||

15 | 10/29 | ||

16 | 10/31 | ||

17 | 11/5 | ||

18 | 11/7 | ||

19 | 11/12 | ||

20 | 11/14 | ||

21 | 11/19 | ||

22 | 11/21 | ||

23 | 11/26 | ||

24 | 12/3 | ||

25 | 12/5 | ||

26 | 12/10 |