CMPT 710 - Computational Complexity - Fall'03
Instructor |
Times & dates |
Homeworks |
Lectures |
Relevant links
- 12/03. The grading scheme for the course is: 60% for
the homeworks, and 40% for the final exam. Below is the list of
the grades for the course: from highest to lowest. The first grade
in each row is the cumulative grade for the course, computed
according to the formula: 60% for HW, and 40% for the final exam.
The second grade in each row is the letter grade derived from
the cumulative grade: A+ for >94%; A for >88%; A- for 85%; B for
<80% (nobody got a B+, since nobody got a cumulative grade between
80% and 85%).
| 95% A+ |
94% A+
89% A
88% A
88% A
85% A-
79% B
75% B
75% B
73% B
You can pick up your HW 4 and your final exam from me in the
next semester (in January). I'll be away from tomorrow until the
end of December.
Have nice holidays!!!
- 12/02. Final exam and HW 4 were graded. The grades for the
course were submitted to the Grad Secretary. If you wish to find out your
grade for the course, please contact the Main Office.
- 11/25. Homework 4 is due in lecture today.
Today's lecture will be overview of the course, and
I'll also talk about the final exam. HW 4 is now posted (see below).
- 11/11. Homework 3 is due this Thursday. The last homework
is available (see below).
- 11/3. This Thursday, Nov. 6, I'll give a talk on "Why
is the P vs NP question still open?" at 1:30pm, in ASB 9705. This is
something that I planned to cover in class, but will unlikely to have
time for. You all are welcome to come to this talk! (The abstract of my
talk can be found
here.)
- 10/20. Homework 2 is due tomorrow. The next homework is
available (see below).
-
Past Announcements
Course information handout: in
PostScript and in
PDF
Course Text:
"Computational Complexity" by Christos H. Papadimitriou,
Addison-Wesley, 1995. (Another good book on computability and
complexity is "Introduction to the Theory of Computation" by
Michael Sipser.)
Instructor:
Valentine Kabanets (kabanets@cs.sfu.ca), Office:
ASB 9921
-
Lectures: Tue 16:30-17:20, Thu 16:30-18:20, in AQ 3154
-
Office Hours: Tue 15:30-16:30,
in ASB 9921 (or by appointment).
Important dates
-
Assignments due: HW 4 is due Nov 25
-
Final exam: TBA
- Homework 1
[ ps ]
[ pdf ]
- Solutions to Homework 1
[ ps ]
[ pdf ]
- Homework 2
[ ps ]
[ pdf ]
- Solutions to Homework 2
[ ps ]
[ pdf ]
- Homework 3
[ ps ]
[ pdf ]
- Solutions to Homework 3
[ ps ]
[ pdf ]
- Homework 4
[ ps ]
[ pdf ]
- Solutions to Homework 4
[ ps ]
[ pdf ]
I will post a
brief outline of what I have
done in class.
- Lecture 1 (intro, background)
[ps]
[pdf]
- Lecture 2 (Time and Space complexity classes)
[ps]
[pdf]
- Lecture 3 (Linear Speedup, Diagonalization)
[ps]
[pdf]
- Lecture 4 (Time and Space Hierarchy, Simulation of Space by Time)
[ps]
[pdf]
- Lecture 5 ("Padding", Nondeterminism)
[ps]
[pdf]
- Lecture 6 (NP-completeness of SAT, coNP)
[ps]
[pdf]
- Lecture 7 (NP-completeness of 3-SAT, NAE-SAT)
[ps]
[pdf]
- Lecture 8 (NP-completeness of 3-COL, NP Search vs. NP decision,
NTime Hierarchy (part 1))
[ps]
[pdf]
- Lecture 9 (NTime Hierarchy Thm (concluded))
[ps]
[pdf]
- Lecture 10 (Savitch's Thm, NL=coNL)
[ps]
[pdf]
- Lecture 11 (PSPACE-completeness of TQBF)
[ps]
[pdf]
- Lecture 12 (Polynomial-Time Hierarchy)
[ps]
[pdf]
- Lecture 13 (Polynomial-Time Hierarchy (cont'd), Circuit Complexity)
[ps]
[pdf]
- Lecture 14 (Circuit class NC)
[ps]
[pdf]
- Lecture 15 (Randomized Computation, RP and BPP)
[ps]
[pdf]
- Lecture 16 (Error reduction in BPP, BPP in P/poly)
[ps]
[pdf]
- Lecture 17 (BPP and P, BPP in PH, Schwartz-Zippel)
[ps]
[pdf]
- Lecture 18 (MA, AM, error reduction for MA)
[ps]
[pdf]
- Lecture 19 (Interactive Protocols (IP), AM protocol for Graph
Nonisomorphism)
[ps]
[pdf]
- Lecture 20 (Interactive Protocols for #SAT,
IP=PSPACE)
[ps]
[pdf]
- Lecture 21 (Hardness of Approximation: Vertex Cover, gap-producing and
gap-preserving reductions, PCP Theorem)
[ps]
[pdf]
- Lecture 22 (PCP Theorem: fragments of the proof)
[ps]
[pdf]