Princeton COS 598C
Analytic Methods in Theoretical Computer Science
Graduate level research seminar
Instructor: Pravesh Kothari
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.
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.
|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|