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

Syllabus:

Introduction

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

NP-Completeness, and Why We Care

Time Hierarchy

The Polynomial Hierarchy (PH)

Space Complexity

Boolean Circuits

Complexity of Counting

Randomized Computation

Interactive Proofs

Complexity and Cryptography

Zero-Knowledge Proofs

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)