Spring'26: Complexity of Computation and Hardness of Approximation (CS 538)

Wednesday: 12:30-15:30
Busch Campus

Instructor: Karthik C. S.

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
Lecture 1	01/21	Models of Computation (Chapter 1), P and NP (Chapter 2; Section 2.1), NP-Completeness (Chapter 2; Sections 2.2, 2.3, and 2.4)
Lecture 2	01/28	Polynomial Time Hierarchy (Chapter 3), Hierarchy theorems (Chapter 4), and Time vs. Space (Chapter 5; Section 5.1)
Lecture 3	02/04	Space bounded complexity (Chapter 5; Sections 5.2, 5.3, and 5.4)
Lecture 4	02/11	Randomized and Counting computation (Chapter 6)
Lecture 5	02/18	Interactive proofs, AM, MA, Zero Knowledge Proofs (Chapter 9)
Lecture 6	02/25	IP = PSPACE Theorem
Lecture 7	03/04	Hardness Amplification
Lecture 8	03/11	PCP Theorem (Algebraic Proof Part I)
	03/18	NO LECTURE
Lecture 9	03/25	PCP Theorem (Algebraic Proof Part II)
Lecture 10	04/01	PCP Theorem (Combinatorial Proof)
Lecture 11	04/08	Hardness of Approximation of Clique and Set Cover
Lecture 12	04/15	Unique Games Conjecture
Lecture 13	04/22	Hardness of Approximation in P Part I
Lecture 14	04/29	Hardness of Approximation in P Part II