Fall'22: Complexity Of Computation (16:198:538)
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 |
| 11/24 | NO LECTURE | ||
| 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
