Instructor: Pravesh K Kothari
Wednesdays, 1:20-4:10 (Engineering D221)
After class (4:10-5:10)
Join the discussion on Ed.
Auditors are welcome. Please email the instructor immediately for access to Ed so that you can receive course announcements.
We will have up to 4 graded homeworks in the class (40% of the grade), and a final project (55% of the grade). 5% of the grade will be class participation.
The homeworks should be typeset (preferably using LaTeX) and submitted via Gradescope.
HW0 is now posted. It contains basic exercises to familiarize yourself with facts from linear algebra and spectral graph theory that we will use without proof in this course. We recommend that you do these exercises yourself. Solutions will be posted in a week.
Your final project should be a lecture notes style exposition of a topic that fits the theme of the class. It is due by May 8, 2026. Suggested topics will be added to the webpage by Spring break. Though the class will differ (especially in the second half), the lectures notes and videos from this Fall 2020 course may be useful. If you prefer watching the videos, we recommend making use of the varying speed settings to adjust the pace (1.5-2x speed may make sense at times).
| Lecture Number | Date | Topic | Notes | Scribe |
|---|---|---|---|---|
| 1 | 01/28/2026 | Introduction, Sum-of-Squares Proofs, Pseudo-Distributions | Notes | Kothari |
| 2 | 02/04/2026 | Sum-of-Squares Algorithm and Application to Max-Cut | Notes | Kothari |
| 3 | 02/11/2026 | |||
| 4 | 02/18/2026 | |||
| 5 | 02/25/2026 | |||
| 6 | 03/04/2026 | |||
| 03/11/2026 | Spring Break | |||
| 7 | 03/18/2026 | |||
| 8 | 03/25/2026 | |||
| 9 | 04/01/2026 | |||
| 10 | 04/08/2026 | |||
| 11 | 04/15/2026 | |||
| 12 | 04/22/2026 |