CMPT 710/CMPT 407 - Computational Complexity - Fall'06
Instructor |
Times & dates |
Homeworks |
Lectures |
Relevant links
- Dec 14: The final exam is graded, and the final course grades
are decided. All are available on the gradebook. (You can pick up your final
from me some time next semester, if you wish.) Have nice holidays!!!
- Dec 4: The final exam is Wed, Dec 13, 15:30-18:30, in AQ 3153. Solutions to HW 4 are now posted.
- Nov 29:
The class tomorrow, Thursday, is cancelled. Please submit your HW 4 to my
office (slide it under the door if I'm not in). Thank you!
- Nov 21:
Homework 4 is now available. Solutions to HW 3 are also posted. I finished
grading Homework 3, and will bring the graded assignments to the class on
Thursday; the grades are available at gradebook.
- Nov 1: I've graded Homework 2 and the midterm. I'll bring them to class tomorrow.
(The grades are available on gradebook, as usual.) Solutions to the midterm are now posted.
- Oct 30: Homework 3 is now available.
-
Oct 19: The solutions to HW 2 are now posted. The midterm will be next
Thursday, Oct 26 (during the regular class time).
-
Oct 12: I've graded Homework 1, and will bring it to class on Tuesday.
(You can access your grades via gradebook.cs.sfu.ca )
-
Oct 3: Solutions to Homework 1 are now posted (see below).
-
Sept 26: Homework 1 is due this Thursday, in class. Homework 2
is now posted; it is due Oct 17.
-
Sept 7: The updated lecture notes for week 1 are now
available. Homework 1 is now available (see below); it is due Sept 28.
-
Sept 5: The lecture notes for week 1 are now available.
Course information handout: in
PostScript and in
PDF
Course Text:
"Computational Complexity" by Christos H. Papadimitriou,
Addison-Wesley, 1995; and "Introduction to the Theory of Computation" by
Michael Sipser.
Instructor:
Valentine Kabanets (kabanets@cs.sfu.ca), Office: 8011
-
Lectures: Tue 11:30-13:20 in WMC 3210, and Thu 11:30-12:20 in RCB 8100
-
Office Hours: Thu 10:00 - 11:00 am,
in TASC I, room 8011 (or by appointment).
Important dates
-
Assignments due: HW 4 is Due Nov 30 (before the class)
-
Midterm: Thursday, Oct 26 (during the lecture time). Note the new date!
-
Final exam: Dec 13, 15:30-18:30, in AQ 3153.
Here are my
lecture notes.
- Week 1 (intro, background)
[ps]
[pdf]
- Week 2 (completeness, complexity classes, linear speedup theorems,
hierarchy theorems)
[ps]
[pdf]
- Week 3 (simulation of space by time, padding, nondeterminism)
[ps]
[pdf]
- Week 4 (NP, co-NP, NP-completeness of SAT and 3-SAT)
[ps]
[pdf]
- Week 5 (NP-completeness (NAE-SAT, 3-COL, Subset Sum), Search-to-Decision reductions)
[ps]
[pdf]
- Week 6 (NTime Hierarchy Thm, Savitch's Thm, NL=coNL, PSPACE-completeness of TQBF (part 1))
[ps]
[pdf]
- Week 7 (PSPACE-completeness of TQBF (part 2), Polytime Hierarchy, circuit complexity)
[ps]
[pdf]
- Week 8 (Parallel computation: NC^1 and AC^0 circuit classes)
[ps]
[pdf]
- Week 9 (Randomized computation (RP and BPP): BPP in P/poly, BPP in Sigma_2)
[ps]
[pdf]
- Week 10 (Polynomial Identity Testing, Schwartz-Zippel, MA, and AM)
[ps]
[pdf]
- Week 11 (MA vs. AM, Graph Nonisomorphism in AM, Interactive Proofs)
[ps]
[pdf]
- Week 12 (#3SAT in IP, PSPACE=IP, Hardness of Approximation and PCP)
[ps]
[pdf]
- Week 13 (The PCP Theorem (fragments of the proof))
[ps]
[pdf]