CPSC468/568: Computational Complexity

Course Information | Course Schedule | Lectures | Homework

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 200

Instructor: Joan Feigenbaum
Office: AKW 512 (51 Prospect Street, New Haven)
Telephone: 203-432-6432
Office hours: 2:30 - 3:30 Tuesdays, 11:00 - 12:00 Thursdays, and by appointment
Assistant: Judi Paige (AKW 507A, 9AM - 2PM, 203-436-1267)

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.

TA: Nicholas Ruozzi
Office: AKW 305
E-mail: firstname.lastname@yale.edu
Office hours: By appointment

Textbooks:

Course Schedule

  1. Thurs, Sept 20: HW1 due
  2. Tues, Oct 2: HW2 due
  3. Thurs, Oct 14: HW3 due
  4. Thurs, Oct 18: Exam 1, in class
  5. Tues, Oct 23: Grades for first three HW assignments and first exam will be available by this date (because the drop date is Friday, Oct 26).
  6. Thrs, Nov 1: HW4 due
  7. Thurs, Nov 15: HW5 due
  8. Thurs, Nov 29: HW6 due
  9. Thurs, Dec 6: Exam 2, in class

Lectures

Note: All references are to Chapters and Appendices in the Arora-Barak webdraft unless otherwise specified.

  1. September 6, 2007: Course outline, introduction [PPT]
  2. September 11, 2007: Review of elementary probability from Appendix A. Turing Machine model and its robustness from Chapter 1.
  3. September 13, 2007: Robustness of the Turing-Machine model, many-to-one polynomial-time reductions, P, NP, coNP, and EXP from Chapters 1 and 2.
  4. September 18, 2007: Cook-Levin Theorem and undecidability of the halting problem from Chapters 1 and 2.
  5. Septembet 20, 2007: Hierarchy theorems, proofs that relativize vs. those that don't, Baker-Gill-Solovay Theorem, sketch of Ladner's Theorem from Chapter 3.
  6. September 25, 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 Chapter 4.
  7. September 27, 2007: Savitch's Theorem, logspace reductions, PATH is NL-complete, defining NL with read-once certificates
  8. October 2, 2007: Review of configuration graphs, the Immerman-Szlepcseny Theorem, definition of Sigma_2^P.
  9. October 4, 2007: Definition of alternating Turing Machines and ATIME(T(n)); three equivalent definitions of the PH from Chapter 5.
  10. October 9, 2007: Introduction to circuit complexity, logspace-uniform circuit families, P/poly, and the Karp-Lipton Theorem from Chapter 6.
  11. October 11, 2007: Definition of randomized, polynomial-time computation and the complexity classes RP, co-RP, ZPP, and BPP. Using Chernoff bounds to achieve exponentially small error probability for any language in BPP. Adleman's proof that BPP is contained in P/poly (from Chapter 7).
  12. October 16, 2007: Sipser and Gacs's proof (using "the probabilistic method") that BPP is contained in both Sigma_2^p and Pi_2^p (from Chapter 7). Brief review for Exam 1.
  13. October 18, 2007: Exam 1.
  14. October 23, 2007: Space-bounded probabilistic computation, UPATH is contained in SL (from Chapter 7). (Note that it is now known that UPATH is in L, but that is not proven in Chapter 7). Introduction to interactive proof systems, GNI is in IP (from Chapter 8).
  15. October 25, 2007: Pairwise-independent, universal hash-function families. Introduction to Arthur-Merlin games (from Chapter 8).
  16. October 30, 2007: Arthur-Merlin Games are as powerful as private-coin interactive proof systems (from the Goldwasser-Sipser paper). Introduction to MIP and oracle proof systems.
  17. November 1, 2007: Using MIP=NEXP to prove that Clique Number is not polynomial-time approximable within a constant factor unless EXP=NEXP. Most of the proof that IP=PSPACE.
  18. November 6, 2007: Finishing the proof that IP=PSPACE. Introduction to the class #P and to the PERMANENT problem (from Chapter 9).
  19. November 8, 2007: Bipartite-matching and cycle-cover interpretations of 0-1 and integer PERMANENT, definitions of the complexity classes PP and partiy-P, introduction to the Valiant-Vazirani lemma and Toda's Theorem (from Chapter 9).
  20. November 13, 2007: Proof of the Valiant-Vazirani lemma (from Chapter 9).
  21. November 15, 2007: Proof of Toda's Theorem, part I (from Chapter 9).
  22. November 27, 2007: Proof of Toda's Theorem, part II (from Chapter 9).
  23. November 29, 2007: One-way functions and the RSA cryptosystem. (This is just for fun and will not be on the December 6 exam.)
  24. December 4, 2007: Review for Exam 2
  25. December 6, 2007: Exam 2

Homework

  1. HW1(due Sept. 20): 1.8, 1.12, 2.3, 2.7, 2.13, 2.21
  2. HW2(due Oct. 2): 2.11, 2.23, 3.4, 4.6, 4.8, 4.9
  3. HW3(due Oct. 14): 4.7, 5.6, 5.8, 6.3, 6.5, 6.11
  4. HW4(due Nov. 1): 7.4, 7.5, 7.8, 8.1, 8.2, 8.7
  5. HW5(due Nov. 15): 8.5, 8.9, 8.10, 8.11, 9.1, 9.5
  6. HW6 (due Nov 29): 9.2, 9.3, 9.6, 9.7, 7.6, 7.7