Fall'22: Complexity Of Computation (16:198:538)

Thursday: 14:00-17:00
Science & Engineering Resource Center - Room 207

This is a graduate complexity theory course. There will be a special emphasis on providing a lot of context to the contents covered in the course. For the first half, we will follow Goldreich's textbook; for the second half, we will use various surveys, research articles, and lecture notes.

Prerequisites: It will be helpful to have some background in algorithms/discrete math, but no formal prerequisite will be enforced. If you do not satisfy the official prerequisites but are still interested in registering for the course, and you are concerned if you will be sufficiently prepared for the course, please send me an email.
The only real prerequisite is some mathematical maturity.

Grading: Scribing lectures (30%), Homework 1 (30%), and Homework 2 (40%).

Please use this latex template for the scribes. For help and feedback on Scribes and Homework, please contact Surya Teja Gavva.

Topics and schedule

Lecture # When Topic Scriber(s)
Lecture 1 09/08 Models of Computation (Chapter 1), P and NP (Chapter 2; Section 2.1) Rohit Rao
Lecture 2 09/15 NP-Completeness (Chapter 2; Sections 2.2, 2.3, and 2.4) Janani Sundaresan
Lecture 3 09/22 Polynomial Time Hierarchy (Chapter 3), Hierarchy theorems (Chapter 4),
and Time vs. Space (Chapter 5; Section 5.1)
Wenyue Hua
Lecture 4 09/29 Space bounded complexity (Chapter 5; Sections 5.2, 5.3, and 5.4) Vikrant Ashvinkumar
Lecture 5 10/06 Randomized and Counting computation (Chapter 6) Mathew Schwartz
Lecture 6 10/13 Interactive proofs, AM, MA, Zero Knowledge Proofs (Chapter 9) Adarsh Srinivasan
Lecture 7 10/20 Guest Lecture by Roei Tell on Circuit Lower Bounds Songhua He
Lecture 8 10/27 IP = PSPACE Theorem Chengyuan Deng
Lecture 9 11/03 Hardness Amplification Sharath Punna
Lecture 10 11/10 PCP Theorem (Algebraic Proof) Parth Mittal
Lecture 11 11/17 PCP Theorem (Combinatorial Proof) Chengyuan Deng
Lecture 12 11/22 Hardness of Approximation of Clique and Set Cover Vihan Shah
Lecture 13 12/01 Unique Games Conjecture Hanna Komlós and Prathamesh Dharangutte
Lecture 14 12/08 Hardness of Approximation in P Janani Sundaresan, Sepehr Assadi,
and Vikrant Ashvinkumar

End of Course Celebration prepared by Surya Teja Gavva

Surya's cake