COMP 531: Theory of Computation
McGill University, Winter 2010
Announcements
April 9: Assignment 5 is out. It's due on April 19 at noon in my office, MC303.
Lectures: Monday and Wednesday 8:30  10:00 in ENGTR 2100.
Instructor:
Phuong Nguyen
Office: McConnell 309 phone: 514 398 7073
303, phone: 514 398 7080,
email: pnguyen@cs.mcgill.ca.
TA: Anil Ada
Office Hours: Monday and Wednesday 34pm in McConnell 309.
Questions via emails are welcome.
Text:
Sanjeev Arora and Boaz Barak "Computation Complexity, A Modern Approach".
A draft of the book on the web.
Reference:
DingZhu Du and KerI Ko: Theory of Computational Complexity.
Links:
Complexity Zoo
Marking scheme: 4 to 5 assignments.
Click here for the course information sheet (.pdf file).
Assignments
Assignment 1 Solution
Assignment 2 Solution Some comments
Assignment 3
Assignment 4
Assignment 5
Lectures
Lecture 1 (January 4): Introduction, very brief discusson on Hilbert's problems, Gödel's Incompleteness Theorems,
diagonalization.
The computation model: Turing machines.
Ref: Sections 1.1, 1.2, 1.3, 1.5.
Lecture 2 (Januray 6): Time and space. Universal Turing machines, the Halting problem.
Class P.
Ref: Sections 1.4 and 1.6.
Lecture 3 (Januray 11): NP, manyone reduction and NPcompleteness. CookLevin Theorem and its proof.
Ref: Sections 2.1  2.4.
Lecture 4 (Januray 13): Complete the proof of CookLevin Theorem. TMSAT. Decision vs Search, and
selfreducibility of NP. coNPcompleteness (Sections 2.5, 2.6.)
Lecture 5 (Januray 18): CookReckhow Theorem, proof systems.
Padding (Section 2.6). Time and Space Hierarchy Theorems (Sections 3.1, 4.1).
Lecture 6 (Januray 20): Nondeterministic Time Hierarchy Theorem,
Ladner's Theorem. Oracle Turing machines (Sections 3.2  3.4).
(Assignment 1 out)
Lecture 7 (January 25): BakerGillSolovay Theorem (Section 3.4).
Quantified Boolean logic and PSPACEcompleteness of QBFTAUT (Sections 4.1, 4.2).
Lecture 8 (January 27): More PSPACEcomplete problems (Du and Ko, section 3.5).
Savitch's Theorem (section 4.2).
The Polynomial hierarchy (sections 5.1, 5.2, 5.5, some more examples can be found in Du and Ko, section 3.3).
Lecture 9 (February 1):
Alternating Turing machines and PH (Section 5.3).
Logspace classes, logspace reduction (Section 4.3) and Pcompleteness (a very brief mention of this is in section 6.7.2;
more can be found in Du and Ko, section 6.7).
Lecture 10 (February 3):
Circuit value problem and some other Pcomplete languages.
PATH and NLcompleteness,
ImmermanSzelepcsenyi Theorem (Section 4.3).
(Assignment 1 due, Assignment 2 out (tomorrow))
Lecture 11 (February 8):
Reingold's Theorem and a very brief outline of the proof (more details are in Chapter 21).
Boolean circuits, Shannon's counting argument,
P/poly, logspace uniformity (sections 6.1, 6.2, 6.5).
Lecture 12 (February 10):
Hierarchy Theorem for Boolean circuits.
Turing machines with advice.
KarpLipton Theorem. (Sections 6.3, 6.4, 6.6.)
Lecture 13 (February 15):
Nonuniform classes NC^k and AC^k (Section 6.7).
Lower bound for AC^0, statement of Håstad Switching Lemma.
Lecture 14 (February 17):
Proof of lower bounds in AC^0 for Parity using Switching Lemma.
Proof of the Switching Lemma. (Section 14.1)
(Assignment 2 due.)
Week February 22  26: Reading week. Assignment 3 out (Wednesday February 24).
Lecture 15 (March 8):
Sublinear time classes.
Dlogtime, Alogtime, Logtime hierarchy LH.
More on uniformity.
Uniform classes AC^0, NC^1, etc.
Lecture 16 (March 15):
Classes ACC, TC0.
RazborovSmolensky Theorem (Section 14.2).
(Assignment 3 due)
Lecture 17 (March 17):
Proof of RazborovSmolensky Theorem.
Lecture 18 (March 19):
Finish proof of RazborovSmolensky Theorem.
Randomized computation: Finding median (Section 7.2.1).
Lecture 19 (March 22):
Probabilistic Primality Testing. ZPP, RP and coRP.
(Sections 7.1, 7.2, 7.3.)
Lecture 20 (March 24):
More on ZPP and RP. BPP. (Sections 7.4, 7.5.)
Assignment 4 out.
Lecture 21 (March 29):
BPP and PH. Classes BPL and RL.
Interactive proof systems. (Sections 7.5, 7.7, 8.1.)
Lecture 22 (March 31):
IP = PSPACE (Section 8.3).
Lecture 23 (April 7):
Finish the proof of IP = PSPACE.
Public coin protocol. (Sections 8.3, 8.2)
(Assignment 4 due)
Lecture 24 (April 12):
Set lower bound protocol. GNI and GI. (Section 8.2)
Lecture 25 (April 14):
Review.
