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.
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.
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% |
We will set up a CTools page were assignments and notices will be posted.
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.