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


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