EECS 574: Computational Complexity Theory

Time: Monday and Wednesday 3:00 pm - 4:30 pm
(Section) Friday 3:30pm - 4:30 pm
Location: 1005 DOW

Instructor: Professor Grant Schoenebeck
Office Hours: BBBB 3640, Monday 4:30-5:30pm; Wednesday 2:00-3:00pm;
Email: "schoeneb"

Graduate Student Instructor: Nan Jiang
Office Hours: BBBB, Friday 2:30-3:30pm
Email: "nanjiang"


Computational complexity studies how "complex" computational problems are where complexity is measured by the amount of a certain resource (e.g time, space) are required to solve the computational problem. For example, which problems can be solved in a small amount of time, and which require a large amount of time. The famous P versus NP problem is but one piece of a much large picture.

This class will explore some of the classical results of computational complexity theory concerning time and space complexity, proof complexity, randomization and approximation. There will be a project at the end of the course allowing students to investigate more recent progress of the field or to add to it.

Topics Covered:

(this list is preliminary)


The class time will be (very) roughly divided into 3 equal sections. Discussion, lecture, and working in small groups.

Reading assignments will be accompanied by brief problem sets that should be completed before lecture. One in-class midterm will be given. Occasionally there may be other (very brief) in-class quizzes. Attendence and participation is manditory. Students should email us at the beginning of the semester if they will miss a class session.

There will also be several problems sets with more challenging problems. A final project will be required that involves either conducting original research or synthesizing recent complexity research on a topics chosen by the student and approved by the professor. Working in small groups on the final project will be permissible but the scope of the project should be appropriate for the size of the group.

A goal of this course is to expose students to a broad range of classical results of computational complexity theory, at a level of understanding so that they can read and understand current research in the area.

Course Text:

Sanjeev Arora and Boaz Barak. Computational Complexity: A modern approach. Cambridge University Press, 2009. Available on-line here (for UMich students and faculty).

The course will cover most of Part I and selected portions of Parts II and III.


EECS 376 is a prerequisite. In particular, it is important that students have experience reading and writing mathematical proofs.

The course will begin by very briefly reviewing Chapter 1 and 2 of the textbook. Students should have already covered most of this material in great depth in the prerequisite course. A good test for student preparedness is reading through these two chapters. A prepared student shoud not struggle greatly to understand the material--either because he has seen it before, or has the mathematical maturity to pick it up from reading the text.


Reading Problem Sets 20%
Participation/Quizes 10%
Problem Sets 20%
Midterm 20%
Final Project 30%

Technology Tools and Policy:


We will set up a CTools page were assignments and notices will be posted.


A Piazza Account will be setup to facilitate discussion outside of class. Act respectfully of the teaching staff and students in all communications on Piazza.

Email Communication:

Send emails to both of the course staff unless there is a reason to send it only to one of us.

Our emails to you will be brief. If a longer discussion is needed, we will likely ask you to come to office hours or schedule a meeting. If you want to discuss your grade, we will also likely ask you to come talk in person.

Put "[EECS 574]" in the subject lines of your email. This will help us attend to your emails more efficiently. If we do not reply to your email within 48 hours, feel free to email me again. Sometimes we get busy and forget to reply to an email.

When you email, we are interacting in a professional context. Use appropriate etiquette including appropriate salutations and signatures. Do not use text message slang or Internet slang.

In Class

No Laptops (or other tech gizmos) in class.

Accommodation for students with disabilities

If you think you need an accommodation for a disability, please let the professor know at your earliest convenience. Some aspects of this course, the assignments, the in-class activities, and the way we teach may be modified to facilitate your participation and progress. As soon as you make us aware of your needs, we can work with the Office of Services for Students with Disabilities (SSD) to help us determine appropriate accommodations. SSD (734-763-3000) typically recommends accommodations through a Verified Individualized Services and Accommodations (VISA) form. We will treat any information you provide as private and confidential.

Academic Integrity

All submitted work must be your own, original work unless you clearly mark it as being otherwise. If you are directly quoting, or building on others' writing, provide a citation. See the Rackham Graduate policy on Academic and Professional Integrity for the definition of plagiarism, and associated consequences.