CS58400 Theory of Computation (Spring 2026)

CS58400 - Theory of Computation and Computational Complexity (Spring 2026)

Course Information

Instructor: Wei Zhan, email: weizhan [AT] purdue [dot] edu
Meetings: Tuesday & Thursday, 12:00 PM - 1:15 PM @ LWSN 1106
Office hours: Tuesday 2:30 PM - 3:30 PM @ DSAI 1100

TA: Satvinder Singh, email: sing1745 [AT] purdue [dot] edu
Office hours: Wednesdays 12:30 - 1:30 PM @ HAAS G040

Course Description

This is an introductory graduate level course on the theory of computation. We will briefly introduce the basics of computability theory that studies what can be computed, and focus more on the complexity theory that studies what can be efficiently computed. We will come across different computation models and recources including time, space, randomness, parallelization and communication, examine the power of corresponding complexity classes and explore the connections between them.

Resources

The course is mostly based on the following optional textbook:

(AB) Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak

For the first part of the course on computability theory, you can refer to:

(Sip) Introduction to the Theory of Computation by Michael Sipser
(HS) Computability and Complexity Theory by Steven Homer and Alan Selman

For futher reading:

Mathematics and Computation by Avi Wigderson
Models of Computation: Exploring the Power of Computing by John Savage
Computational Complexity: A Conceptual Perspective by Oded Goldreich
Complexity Zoo: an encyclopedia of complexity classes

Grading

Homework (4 assignments): 10% each, 40% total;
Midterm exam: 25%;
Final Exam: 35%.

Detailed policies can be found here.

Course Schedule

Note: the schedule below is tentative and will be updated along the course progression.

Date	Topic	Material
Tue. Jan 13	Course overview, Turing machines	(AB) 1.2
Thu. Jan 15	Universal Turing machine	(AB) 1.3, 1.A
Tue. Jan 20	Decidability, diagonalization, R and RE	(AB) 1.5, (Sip) 4.2
Thu. Jan 22	Halting problem, many-one reduction, Rice's theorem	(Sip) 5.1, 5.2, 5.3
Tue. Jan 27	Oracle machines, Turing reduction, arithmetic hierarchy	(Sip) 6.3, (HS) 3.9
Thu. Jan 29	Post's theorem	(HS) 3.9, Problem Set 1 (Due: Feb 19)
Tue. Feb 3	Time complexity, P and NP	(AB) 1.6, 2.1
Thu. Feb 5	Polynomial-time reduction, Cook-Levin thoerem	(AB) 2.2, 2.3, 2.4
Tue. Feb 10	EXP and NEXP, time hierarchy theorems	(AB) 2.6, 3.1, 3.2
Thu. Feb 12	Ladner's theorem, Mahaney's theorem	(AB) 3.3, exposition by Joshua Grochow
Tue. Feb 17	Polynomial hierarchy
Thu. Feb 19	Space complexity, PSPACE	Problem Set 2 (Due: Mar 12)
Tue. Feb 24	Savitch's Theorem
Thu. Feb 26	NL=coNL
Tue. Mar 3	Randomized computation, RP and BPP
Thu. Mar 5	Midterm exam
Tue. Mar 10	Valiant-Vazirani Theorem
Thu. Mar 12	#P, Toda's theorem	Problem Set 3 (Due: Apr 2)
Tue. Mar 24	Interactive proofs, Arthur and Merlin
Thu. Mar 26	IP=PSPACE
Tue. Mar 31	Certificate and query complexity
Thu. Apr 2	Relativization barrier	Problem Set 4 (Due: Apr 23)
Tue. Apr 7	Formulae and circuits
Thu. Apr 9	Karp-Lipton Theorem
Tue. Apr 14	Håstad's switching lemma
Thu. Apr 16	Natural proof barrier
Tue. Apr 21	Communication complexity
Thu. Apr 23	Karchmer-Wigderson games
Tue. Apr 28	Branching programs, Barrington's theorem
Thu. Apr 30	Summary and more
TBD	Final exam