Home Page


EECS 574
          Graphics

CSE 574: Computational Complexity (Winter 2025)

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.


"Official Prerequisites": Graduate standing or EECS 376.


Important pre-req note: In Winter 2025, for the first time we will also offer an undergraduate level "Computability and Complexity" course (taught as a 498 by Prof. Nikhil Bansal). Undergraduate students are advised to take that course instead of CSE 574. If you are an undergraduate student, you should take 498 instead, which is designed and streamlined specifically for the background knowledge of undergraduate students. For 574, it helps a lot to have a general understanding of theory of computation (to the level of a good textbook on the subject such as "Introduction to the Theory of Computation" by M. Sipser, or the first few chapters of our textbook by Arora and Barak below).


Instructor: Mahdi Cheraghchi


Planned Syllabus:


  1. Introduction, quick refreshers (deterministic and non-deterministic time, P, NP, NP-completeness)

  2. Time Hierarchy

  3. The Polynomial Hierarchy (PH)

  4. Space Complexity

  5. Boolean Circuits

  6. Randomized Computation

  7. Interactive Proofs

  8. Zero-Knowledge Proofs

  9. Probabilistically Checkable Proofs (PCPs)
  10. Hardness of Approximation

  11. Special topics

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


Evaluation criteria: Participation, Homework, Midterm Exam, Scribe Notes (students collectively create lecture notes as the course proceeds), Final Project.


Lectures: Mon/Wed 3:00 PM - 4:30 PM at 1010 DOW (from Jan 8, 2025 to Apr 22, 2025)


Discussions: Fri 3:30-4:30PM at 1109 FXB (from Jan 8, 2025 to Apr 22, 2025)

If you're an undergraduate student and really need to take 574 instead of the undergraduate version 498 (see "
Important pre-req note" above): You'll need to ask for permission to get ULCS/MDE credit. Details are below.
How to request permission to get ULCS or MDE credit for a graduate-level course:

Undergraduate students with interests in research, graduate studies, and/or deeper investigation into specific areas of CS can request permission to use credits from graduate-level EECS courses towards credit requirements for ULCS (for courses emphasizing individual work) or MDE/capstone (for courses emphasizing team projects).

To request permission to get ULCS or MDE credit for a graduate-level class, you should email the CPA for your program (csengadvisor@umich.edu for CoE students, cslsaadvisor@umich.edu for LSA students).  In your email, you should identify yourself, the graduate-level course, which kind of credit you are requesting (ULCS or MDE), and how your request satisfies the following evaluation criteria:

Timing: You must submit a request prior to the first day of classes in the semester that you take the graduate-level course.  Requests will not be granted retroactively.

Academic Standing: Your academic record at the time of your request should be strong - comparable to the record that a CSE graduate student could have had at a similar point in their undergraduate career.

Preparation: You should have done well in (and/or currently be doing well in) coursework that will prepare you to be successful in the graduate-level course.  For example, for a graduate-level course covering advanced topics in area X, you should first take and do well in an undergraduate introductory course on X if one is offered, and if not, in CS core course(s) most closely related to area X.

Purpose: You should have a (brief) reason for why you want to take this course in particular. Typical examples of reasons are: that you are planning to apply to graduate school to study the field covered in the course; that you are working on undergraduate research in the area the course covers; that you took the introductory course in the topic and the professor of that course personally encouraged you to take this graduate-level course.

Complementarity: If you are pursuing another major or minor besides CS, the graduate-level course should make a distinctive contribution specifically to your CS degree. A graduate-level course that overlaps with coursework you have taken for another major/minor, or that also satisfies requirements for another major/minor, would in general not be approved.  (Note: This does not mean you cannot take such a graduate-level class - it just means you would not be allowed to use it to satisfy ULCS/MDE credit requirements.)


Home Page