CMPT 710/CMPT 407 - Computational Complexity - Fall'07
Instructor |
Times & dates |
Homeworks |
Lectures
- Dec 9: The final exams are now graded; the grades for the final
exam as well as the final grades for the course are
available at gradebook.
- Dec 5: HW 3 and HW 4 are now graded, and the grades are available at gradebook.
I'll have an office hour tomorrow (Thursday), 1-2pm, and you're welcome to stop by to pick up
your assignments and to ask questions on the course material. Good luck at the final exam this Friday!
- Dec 4: Solutions to HW 4 are now posted.
- Nov 20: Homework 4 is now posted. It is due by Dec 4. Note that the
last class is Nov 29, and you may hand in your HW 4 then. But if you wish, you
may hand it in during the office hour on Dec 4. (You can also submit your HW
electronically, by emailing me a pdf file.) Also, the solutions to HW
3 are now posted.
- Nov 1: Homework 3 is now posted. It is due by Nov 15. The solutions
to homework 2 are also posted.
- Oct 5: Homework 2 is now posted; it is due by Oct 25.
- Oct 3: I've finished grading the first homework. I'll return it in
class tomorrow. The grades can be viewed on the gradebook (gradebook.cs.sfu.ca).
-
Oct 2:
Next Thursday (Oct 11) we have a midterm exam (during the regular class time). It will
cover the lecture material up to (including) Lecture 10 (see the lecture
notes below). There will be both problems (similar to HW 1, but easier)
and questions asking you to give
definitions and statements of some complexity theorems. The midterm will be 2
hours (but you may, and probably will, finish earlier). I am away at a
conference next week. One of my grad students will proctor the midterm for me.
Also, since I'm away next week, there won't be any class next Tuesday, Oct 9.
- Sep 10: We now have new lecture rooms!
Tuesday class is in AQ 2104, and Thursday class is in WMC 2200. (Note the
rooms are different for Tue and Thu.) The class times remain the same. See you
in AQ 2104 for tomorrow's lecture!
-
Sep 6: The first homework assignment is now available (see below). It is
due Sept 27, at the beginning of the lecture. (You can already start working on
problems 1 and 4. For the remaining two, you need to wait for a couple of lectures.)
-
Sep 5: An update on the room: We're still searching for a different room
for the class. I will talk about it during the lecture tomorrow. For now,
we will continue meeting in the same room as last time, RCB 6136.
-
Sep 4: The lecture notes for the first lecture are now posted
(see below). I've enquired about a possible room change. As soon as I
find out our options, I'll post them here.
-
Aug 27: The first lecture is on Tuesday, Sept 4. If you're
interested in taking this course, but have some conflicts please email
me and/or come to the first class where we can discuss the course
time and location.
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. (However, we will mostly use
my lecture notes, which will be available on-line.)
Instructor:
Valentine Kabanets (kabanets@cs.sfu.ca), Office: 8011 (in TASC 1)
-
Lectures: Tue 11:30-12:20 in AQ 2104 and
Thu 11:30-13:20 in WMC 2200
-
Office Hours: Tue 12:30-13:30 in TASC 1 # 8011
(or by appointment; email me to set up an appointment)
Important dates
-
Assignments due: HW 4 is due Dec 4
-
Midterm: Thu Oct 11
-
Final exam: Fri Dec 7, 15:30-18:30, AQ 3154
Here are my
lecture notes.
- 04/09: Lecture 1 (Intro)
[pdf]
- 06/09: Lecture 2 (Review: Languages and Turing machines)
[pdf]
- 11/09: Lecture 3 (Review: Reductions and Time Complexity)
[pdf]
- 13/09: Lecture 4 (Complexity classes,
Completeness, Linear Speedup, and Hierarchy Theorems)
[pdf]
- 18/09: Lecture 5 (Simulating Space by Time, "Padding")
[pdf]
- 20/09: Lecture 6
(Nondeterminism, NP, NP-completeness of Circuit-SAT)
[pdf]
- 25/09: Lecture 7 (NP-completeness of SAT, preview of the PCP
Theorem)
[pdf]
- 27/09:
Lecture 8 (co-NP completeness, NP-completeness of 3-SAT, and NAE-SAT)
[pdf]
- 02/10: Lecture 9
(NP completeness of 3-COL and SubsetSum)
[pdf]
- 04/10: Lecture 10
(Search-to-Decision reductions, Nondeterministic Time Hierarchy)
[pdf]
- 09/10: no lecture
- 11/10: midterm
- 16/10: Lecture 11
(Nondeterministic LogSpace: Savitch's theorem)
[pdf]
- 18/19: Lecture 12
(NL=coNL and PSPACE-completeness of TQBF)
[pdf]
- 23/10: Lecture 13
(PSPACE-completeness of TQBF (cont'd))
[pdf]
- 25/10: Lecture 14
(Polytime hierarchy and circuit complexity)
[pdf]
- 30/10: Lecture 15
(Circuit complexity: NC and AC_0)
[pdf]
- 01/11: Lecture 16
(Randomized complexity: RP and BPP)
[pdf]
- 06/11: Lecture 17
(Randomized complexity: error reduction for BPP, and BPP in P/poly)
[pdf]
- 08/11: Lecture 18
(BPP vs. P, BPP in PH, and Poly Identity Testing)
[pdf]
- 13/11: Lecture 19
(Randomized NP)
[pdf]
- 15/11: Lecture 20
(Interactive Proof Systems, Graph NonIsomorphism)
[pdf]
- 20/11: Lecture 21
(#SAT in IP)
[pdf]
- 22/11: Lecture 22
(#SAT in IP (cont'd), IP=PSPACE, and definition of PCP(r,q))
[pdf]
- 27/11: Lecture 23
(Hardness of approximation)
[pdf]
- 29/11: Lecture 24
(PCP Theorem: Fragments of the proof)
[pdf]