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	(AB) 5.2, 5.5
Thu. Feb 19	Space complexity, Savitch's theorem	(AB) 4.1, 4.2, Problem Set 2 (Due: Mar 12)
Tue. Feb 24	Immerman–Szelepcsényi theorem	(AB) 4.3
Thu. Feb 26	Time-space tradeoff lower bounds	(AB) 5.4, Kannan's original paper
Tue. Mar 3	Randomized computation, RP and BPP	(AB) 7.1, 7.3, 7.4, 7.7
Thu. Mar 5	Midterm exam
Tue. Mar 10	BPP vs. NP, Valiant-Vazirani theorem	(AB) 7.5
Thu. Mar 12	#P, Toda's theorem	(AB) 17.2, 17.3, 17.4, Problem Set 3 (Due: Apr 2)
Tue. Mar 17	No class (spring break)
Thu. Mar 19	No class (spring break)
Tue. Mar 24	Interactive proofs, IP=PSPACE	(AB) 8.1, 8.3
Thu. Mar 26	Arthur and Merlin	(AB) 8.2
Tue. Mar 31	Circuit complexity
Thu. Apr 2	Karp-Lipton theorem, Adleman's theorem	Problem Set 4 (Due: Apr 23)
Tue. Apr 7	NC and AC, Håstad's switching lemma
Thu. Apr 9	Natural proof barrier
Tue. Apr 14	Query complexity
Thu. Apr 16	Relativization 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
Tue. May 5	Final exam