CPSC468/568: Computational Complexity

Reading Assignments | Course Information | Lectures | Homework

Reading Assignments

  1. January 18, 2007: In the (online) Arora-Barak book, read sections 1.3, 1.4, 1.5, and 1.A carefully. Also skim the Introduction and the rest of Chapter 1.
  2. Jan 22, 2007: In Arora-Barak, read Sections 2.4, 2.5, 2.6, and 2.7 carefully. Sections 2.1, 2.2, and 2.3 will be covered in class, but you should skim those as well.
  3. Jan 30, 2007: Read chapter 3 of Arora-Barak; Sections 3.3 and 3.4 should be read most carefully.
  4. Feb 6, 2007: Read chapter 4 of Arora-Barak, paying special attention to sections 4.3 (just before Savitch's theorem) and 4.3.2 (on PSPACE and games), and the proofs of Theorem 4.11 and Lemma 5.15.
  5. Feb 15, 2007: Read chapter 6 of Arora-Barak.
  6. Mar 27, 2007: Read Chapter 8 of Arora-Barak.
  7. 7. Apr 10, 2007: Scrutinize the proof that 0-1 PERM is #P-complete (in Chapter 9 of Arora-Barak) and review the proof of the Cook-Levin Theorem (in Chapter 2 of Arora-Barak).

Course information

Description: Introduction to the theory of computational complexity. Basic complexity classes, including polynomial time, nondeterministic polynomial time, probabilistic polynomial time, polynomial space, logarithmic space, and nondeterministic logarithmic space. The roles of reductions, completeness, randomness, and interaction in the formal study of computation.

T/Th, 1:00 - 2:15 p.m., AKW 500

Further details are available in the slides for the first lecture. [PPT]

Instructor: Joan Feigenbaum
Office: AKW 512
Telephone: 203-432-6432
Office hours: Tuesday 4-5PM; Thursday 9-10AM
Note: Professor Feigenbaum suffers from Repetitive Strain Injury and cannot handle large amounts of email. Do NOT send her email about CPSC468/568; instead, please contact her by phone, through the TA, or through her assistant Judi Paige (Tel: 203-436-1267, email: Judi.Paige@yale.edu).

TA: Nikhil Srivastava
Office: AKW 203
Telephone: 203-432-1245
E-mail: firstname.lastname@yale.edu
Office hours: Tuesday 930-1030am, Friday 10-11am

Textbooks:

Lectures

  1. Jan 16, 2007: Course outline, introduction [PPT]
  2. Jan 18, 2007: Introduction to Complexity Classes [PPT]
  3. Jan 23, 2007: Robustness of the Turing-Machine model, many-to-one polynomial-time reductions, P, NP, and reduction from SAT to 3SAT (from [AB, chapters 1 and 2])
  4. Jan 25, 2007: Proof that SAT is NP-Complete (from [AB, chapter 2])
  5. Jan 30, 2007: Diagonalization, basic hierarchy theorems, proofs that relativize vs. those that don't, statement and proof of the Baker-Gill-Solovay Theorem, statement of Ladner's Theorem (from [AB], chapter 3)
  6. Feb 1, 2007: Space complexity; the classes PSPACE, L, and NL; statement and proof that PATH is in NL; introduction to the PSPACE-complete problem TQBF (from [AB], chapter 4)
  7. Feb 6, 2007: PATH is NL-complete, "read-once-certificates" definition of NL, Savitch's Theorem (from [AB, chapter 4])
  8. Feb 8, 2007: The Immerman-Szlepcsenyi Theorem, review of the essentials of space-complexity (from [AB, chapter 4]), introduction to the Polynomial Hierarchy (from [AB, chapter 5]).
  9. Feb 13, 2007: Proofs of Berman's Theorem and Rice's Theorem (from solutions to Homework 1).
  10. Feb 15, 2007: Definition of alternating Turing Machines and ATIME(T(n)), three equivalent definitions of the PH (from [AB, chapter 5]); introduction to circuit complexity and P/poly (from [AB, chapter 6]).
  11. Feb 20, 2007: Turing machines that take advice, the Karp-Lipton Theorem, logspace-uniform circuit families, and the complexity classes NC and AC (from [AB, chapter 6]).
  12. Feb 22, 2007: Probabilistic Turing machines; the complexity classes RP, co-RP, ZPP, and BPP; applying the Chernoff bound on the tails of the binomial distribution; BPP is contained in P/poly (from [AB, chapter 7]).
  13. Feb 27, 2007: Review for Exam 1
  14. Mar 1, 2007: Exam 1
  15. Mar 6, 2007: Review of Question 4 from Exam 1. Proof that BPP is contained in Sigma_2^P and in Pi_2^P (from [AB, Chapter 7]).
  16. Mar 8, 2007: Space-bounded, probabilistic computation; the complexity classes RL, coRL, BPL, and SL; PATH is in SL (from [AB, Chapter7]); the complexity class IP and the proof that GNI (graph non-isomorphism) is in IP (from [AB, Chapter 8]).
  17. Mar 27, 2007: Pairwise-independent hash-function collections; Goldwasser-Sipser Set Lowerbound proofs (from [AB, Chapter 8]).
  18. Mar 29, 2007: Public coins are as powerful as private coins in interactive proof systems; specifically, IP[k] is contained in AM[k+2] (from a paper by Goldwasser and Sipser that was distributed in class).
  19. Apr 3, 2007: IP = PSPACE. [PPT]
  20. Apr 5, 2007: Connection between MIP=NEXP and nonapproximability of CLIQUE; introduction to the complexity class #P.
  21. Apr 10, 2007: Interpretations of 0-1 PERM in terms of perfect matchings and integer PERM in terms of cycle covers, proof that 0-1 PERM is #P-complete (from [AB, Chapter 9]).
  22. Apr 12, 2007: Valiant-Vazirani theorem (from [AB, Chapter 9]).
  23. Apr 17, 2007: Toda's Theorem (from [AB, Chapter 9]).
  24. Apr 19, 2007: Communication complexity; fooling sets; linear lower bound on the communication complexity of set disjointness; relationship with streaming space complexity.
  25. Apr 24, 2007: Review for Exam 2.
  26. Apr 26, 2007: Exam 2

Homework

  1. HW1 (due Feb 1): Problems 1.1, 1.8, 1.12, 1.15, 2.3, 2.4, 2.7, 2.13, 2.17, and 2.21.
  2. HW2 (due Feb 13): Problems 3.2, 3.4, 3.6, 4.1, 4.2, 4.4, 4.5, 4.6, 4.8, 4.9.
  3. HW3 (due Feb 22): Problems 5.4, 5.8, 6.9, 6.11, 6.13.
  4. HW4 (due April 10): Problems 8.1, 8.2, 8.9, 8.10, 8.11, 9.1, and 9.5.
  5. HW5 (due April 22): 9.2, 9.3, 12.2., 12.3, 12.5, 12.7, 12.8.