CMPT 710
Computational Complexity - Spring 2015
- 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!
- 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%
Note: I will post 4 homework assignments (one before each quiz),
which will not be collected and graded. The solutions to homework problems will be posted
before the quiz. The quizzes will be loosely based
on the homework problems, so you will benefit
by solving the homework problems by yourself!
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
I'll post homework assignments & solutions.
I'll post my lecture notes for each class,
and a reading assignment.