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


Thursday: 14:00-17:00

This course will serve as an introductory graduate complexity theory course. There will be a special emphasis on providing a lot of context to the contents covered in the course. We will follow Wigderson's book and Goldreich's book. Additionally, the homeworks will serve the purpose of equipping the student with the requisite tools and background to better understand the lectures instead of serving as verfication mechanisms to see if the students have understood the course materials.

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.

Tentative list of topics that will be covered: Turing machines, Complexity Classes, P, NP, Cook-Levin Theorem, Hierarchy theorems, Ladner’s Theorem, Oracles and relativization, Space bounded complexity, NL, co-NL, Polynomial Hierarchy and alternating Turing machines, Randomized computation, Interactive proofs, AM, MA, Goldwasser-Sipser set lower bound protocol, IP = PSPACE theorem, PCP Theorem.

Grading: Scribing lectures (30%), Homework (70%).

Topics and schedule


# When Scriber(s) Topic
1 09/08 Models of Computation
2 09/15
3 09/22
4 09/29
5 10/06
6 10/13
7 10/20
8 10/27
9 11/03
10 11/10
11 11/17
12 11/22
11/24 NO LECTURE
13 12/01
14 12/08