CMPT 710
Computational Complexity - Spring 2015
Announcements
- Jan 7: This course is very likely to be cross-listed with cmpt 407 very soon. You will be getting emails once this happens. Meanwhile, let's move the next lecture (this Thu) already to be joint with cmpt 407: the time is 12:30-14:20, and the room is BLU 10021. See you there this Thu!
older announcements...
- Jan 4: The first class is Tue, Jan 6.
Course description
The main goal of Complexity Theory is to answer the question: What can be efficiently computed given limited resources? This is a more "practical" version of the main question of Computability Theory: What can be computed? In this course, we will see a rich landscape of complexity classes that are used to characterize problems according to the required resources (such as time, space, randomness, parallelism). We will discuss some known and conjectured relationships among these classes, obtaining a detailed map of the complexity world. Proving the correctness of this map would involve solving some of the deepest open problems in computer science, including the famous "P vs. NP" question.
- Topics
- Texts
- Lectures
- Office hours
- Marking scheme
- basic complexity classes (time, space, nondeterminism)
- circuit complexity
- NP-completeness
- randomized computation complexity
- polynomial-time hierarchy
- counting classes
- interactive proofs
- the PCP theorem
- barriers in complexity (relativization and natural proofs)
- Computational Complexity: A modern approach by Sanjeev Arora and Boaz Barak, Cambridge University Press, 2009. [a new textbook, containing many recent results in complexity]
- Computational Complexity by Christos H. Papadimitriou, Addison-Wesley, 1995. [a classic; very comprehensive coverage]
- Introduction to the Theory of Computation by Michael Sipser, 2012, 9781133187790. [intro into computability and complexity]
| day | time | room |
|---|---|---|
| Tue | 9:30-10:20 | SECB 1012 |
| Thu | 9:30-11:20 | SECB 1012 |
- 4 in-class quizzes, worth 15% each,
- final exam, worth 40%
Teaching staff
Instructor: Valentine Kabanets (kabanets@cs.sfu.ca), Office: TASC1 8011
Important dates
The 50-minute quizzes will be given during our regular lectures on the following dates.
| Quiz 1 | Quiz 2 | Quiz 3 | Quiz 4 |
|---|---|---|---|
| Feb 3 | Feb 24 | Mar 17 | Apr 7 |
Final exam: Sat, Apr 18, 15:30-18:30, room TBA
Assignments
I'll post homework assignments & solutions.
Lecture notes
I'll post my lecture notes for each class, and a reading assignment.