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 3--4pm 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: Ding-Zhu Du and Ker-I 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, many-one reduction and NP-completeness. Cook--Levin Theorem and its proof. Ref: Sections 2.1 - 2.4.
Lecture 4 (Januray 13): Complete the proof of Cook--Levin Theorem. TMSAT. Decision vs Search, and self-reducibility of NP. coNP-completeness (Sections 2.5, 2.6.)
Lecture 5 (Januray 18): Cook--Reckhow 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): Baker--Gill--Solovay Theorem (Section 3.4). Quantified Boolean logic and PSPACE-completeness of QBF-TAUT (Sections 4.1, 4.2).
Lecture 8 (January 27): More PSPACE-complete 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 P-completeness (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 P-complete languages. PATH and NL-completeness, Immerman--Szelepcsenyi 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. Karp--Lipton Theorem. (Sections 6.3, 6.4, 6.6.)
Lecture 13 (February 15): Non-uniform 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. Razborov-Smolensky Theorem (Section 14.2). (Assignment 3 due)
Lecture 17 (March 17): Proof of Razborov-Smolensky Theorem.
Lecture 18 (March 19): Finish proof of Razborov-Smolensky Theorem. Randomized computation: Finding median (Section 7.2.1).
Lecture 19 (March 22): Probabilistic Primality Testing. ZPP, RP and co-RP. (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.