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

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

For futher reading:

Mathematics and Computation by Avi Wigderson

Models of Computation: Exploring the Power of Computing by John Savage

Grading

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

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
Thu. Jan 15	Universal Turing machine
Tue. Jan 20	Languages, decidability, diagonalization
Thu. Jan 22	Halting problem, R and RE
Tue. Jan 27	Many to one reduction, Rice's theorem
Thu. Jan 29	Oracle machines, Turing reduction	Problem Set 1 (Due: Feb 19)
Tue. Feb 3	Time complexity, P and NP
Thu. Feb 5	Polynomial-time reduction, Cook-Levin thoerem
Tue. Feb 10	EXP and NEXP, time hierarchy theorems
Thu. Feb 12	NP-intermediate, Ladner's theorem
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	Relativization barrier
Thu. Mar 5	Midterm exam
Tue. Mar 10	Randomized computation, RP and BPP
Thu. Mar 12	Valiant-Vazirani Theorem	Problem Set 3 (Due: Apr 2)
Tue. Mar 24	#P, Toda's theorem
Thu. Mar 26	Interactive proofs, Authur and Merlin
Tue. Mar 31	IP=PSPACE
Thu. Apr 2	Formulae and circuits	Problem Set 4 (Due: Apr 23)
Tue. Apr 7	Karp-Lipton Theorem
Thu. Apr 9	Håstad's switching lemma
Tue. Apr 14	Natural proof barrier
Thu. Apr 16	Certificate and query complexity
Tue. Apr 21	Randomized query complexity
Thu. Apr 23	Communication complexity
Tue. Apr 28	Randomized communication complexity
Thu. Apr 30	Karchmer-Wigderson games
TBD	Final exam