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
Planned Syllabus (may be adapted depending on how fast we go and the interests and preferences of students):
Time and Non-deterministic Time: The Million-dollar Question
NP-Completeness, and Why We Care
The Polynomial Hierarchy (PH)
Complexity of Counting
Interactive Proofs (and possibly Zero-Knowledge Proofs)
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 1017 DOW (from Aug 30, 2021 to Dec 10, 2021)
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 (firstname.lastname@example.org for CoE students, email@example.com 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.)