Home Page

EECS 574

EECS 574: Computational Complexity (Fall 2021)

Overview: This course explores the story of computation after Alan Turing. The notion of Turing Machines provides a mathematical abstraction of what it means to compute. In principle, it captures all computing devices that we know of or will ever come up with. Computational complexity takes a step further and also takes into consideration the fact that computers are limited in resources, such as time, memory, or randomness. The phenomenon of computing becomes much more nuanced with limited resources in mind. Which computational problems can or cannot be solved with limited resources? That is what computational complexity aims to study.

Instructor: Mahdi Cheraghchi


  1. Introduction

  2. Time and Non-deterministic Time: The Million-dollar Question

  3. NP-Completeness, and Why We Care

  4. Time Hierarchy

  5. The Polynomial Hierarchy (PH)

  6. Space Complexity

  7. Boolean Circuits

  8. Complexity of Counting

  9. Randomized Computation

  10. Interactive Proofs

  11. Complexity and Cryptography

  12. Zero-Knowledge Proofs

  13. Hardness of Approximation

Required textbook: Arora and Barak: “Computational Complexity: A Modern Approach”, Cambridge University Press.

Prerequisites: Graduate standing or EECS 376.

Evaluation criteria: Participation, Homework, Midterm Exam, Scribe Notes, Final Project.

Lectures: Mon/Wed 3:00 PM - 4:30 PM at 2150 DOW (from Aug 30, 2021 to Dec 10, 2021)

Home Page