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
Time and Non-deterministic Time: The Million-dollar Question
NP-Completeness, and Why We Care
The Polynomial Hierarchy (PH)
Complexity of Counting
Complexity and Cryptography
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)