Princeton COS 598C
Analytic Methods in Theoretical Computer Science

Graduate level research seminar

Instructor: Pravesh Kothari

Course Summary

Syllabus: This is a research oriented seminar in theoretical computer science aimed at understanding important recent works that rely on generally applicable analytical methods.

The first part of the class will focus on the Unique Games Conjecture and its relationship to the complexity of expansion and related problems in graphs. We will see the use of the sum-of-squares method and low-distortion metric embeddings in algorithm design for such problems. We will also see Fourier analysis and isoperimetric inequalities that underlie some sharp hardness results based on the UGC.

In the second part of the seminar, we will focus on studying important recent papers that build on and use the above tools.

Prerequisites: Mathematical maturity and proficiency in undergraduate linear algebra. Graduate level classes in theoretical computer science such as COS 521/522 will help appreciate the content better. Listeners and Auditors are welcome.

Participant Lectures The second half of the seminar will involve participant lectures. The schedule and topics will be decided after an in-class discussion.

Administrative Information

Lectures: Mondays and Wednesdays 01:30 pm - 02:50 pm in Friend Center 009.
Office Hours: Immediately after class, 194 Nassau St, Room 219 or by appointment.

Piazza: Course discussion and questions will be managed through Piazza. Please sign up here.

Coursework: Two lectures per week. Participants will be expected to prepare a presentation and lecture notes on one topic. There are no graded assignments/tests for this class. Problem sets will be handed out but will not be graded.


Lecture notes, relevant papers/surveys and notes from related classes will be posted on the class webpage.

Links to Classes on Related Topics
Luca Trevisan's Class at Berkeley
Moses Charikar's Class at Stanford.
Ryan O'Donnell's Class at CMU.
My class from 2016 (co-taught with David Steurer)

Lecture # Topic Notes Further Reading
UGC and Complexity of Expansion Problems
1. 02/04 Introduction Lecture 1 Notes
2. 02/06 Edge Expansion and Eigenvalues: Cheeger's Inequality Handouts 3 and 4 from Trevisan's class.
3. 02/11 Spectrum of Cayley Graphs: Tightness of Cheeger's Inequality Handout from Luca Trevisan's Class
4. 02/13 The Sum-of-Squares Method: Goemans-Williamson Rounding Handouts from the 2016 SoS Seminar: Basic Definitions and Application to Max-Cut
4. 02/18 SoS Method Ctd.
4. 02/20 Arora-Rao-Vazirani algorithm for Graph Expansion I Lecture Notes
5. 02/25 Arora-Rao-Vazirani algorithm for Graph Expansion II
5. 02/27 UGC Hardness via Dictator vs Quasirandom Tests I Lecture Notes
6. 03/06 UGC Hardness via Dictator vs Quasirandom Tests II Lecture Notes
7. 03/11 UGC Hardness of Max-Cut