CMPT 710 - Computational Complexity - Fall'05
Instructor |
Times & dates |
Homeworks |
Lectures |
Relevant links
- 12/09. I finished grading the final exam. The grades are
posted on the gradebook. I've also posted there the final grades for
the course. (The assignment of final course grades depending on the
cumulative percentage was as follows: >91% = A+; >82% = A; >70% = B; >
64% = B-; >50% = C.) Happy holidays!
- 12/06. HW 4 is now graded; the grades are available from the Gradebook. I'll return HW 4 tomorrow
after the final exam.
- 12/05. Solutions to HW 4 are now posted.
- 12/01. Final Exam is scheduled for December 7, Wednesday, 1-4pm, in AQ 2109.
- 11/22. Solutions to Homework 3 are now posted (see below).
- 11/21. Homework 4 is now available (see below).
- 11/10. The statement of Problem 2 on Homework 3 is now
corrected. The updated version of the homework is available below
(under Homeworks). Thanks to Sushmita for pointing out an error in
the earlier version of the problem!
- 11/2. Homework 3 is now available.
- 10/27. Solutions to the midterm are now posted.
- 10/22. Solutions to Homework 2 are now posted.
- 10/20. The midterm will be next Thursday (Oct 27). The topics covered will
be primarily those covered on the first two homework assignments, plus some simple questions
on the topics discussed in class up to and including Week 7.
- 10/11. Solutions to Homework 1 are now posted. The grades
for HW 1 are available from the Gradebook (gradebook.cs.sfu.ca).
- 10/3. Homework 2 is now available.
09/27. The homework is due this Thursday (at the start of the
class).
- 09/13. The first homework assignment is now posted (see
below). It is due Sept 29.
- 09/05.
The first class is tomorrow, Sept 6.
-
Past Announcements
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 & Thu 13:00-14:20 in AQ 5005
-
Office Hours: Tue 12:00-13:00,
in 8011 (or by appointment).
Important dates
-
Assignments due: HW3 is due Nov 17 (at the beginning of the class)
-
Midterm: October 27 (Thursday)
-
Final exam: December 7, Wednesday, 1-4pm, in AQ 2109.
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]