CPSC468/568: Computational Complexity (Fall 2012)



Time: TTh, 2:30 - 3:45
Location: AKW 000
Instructor: Joan Feigenbaum
Professor Feigenbaum's Office Hours: Thurs 10:30 a.m. to 12:30 p.m. in AKW 512 or by appointment
Professor Feigenbaum's Assistant: Judi Paige (AKW 507A, Judi.Paige@yale.edu, 203-436-1267)
TA: Aaron Segal (AKW 503, Aaron.Segal@yale.edu)
TA's Office Hours: Tues and Thurs 4:00 to 5:00 p.m. in AKW 503 or by appointment
Textbook: Computational Complexity, A Modern Approach, by Sanjeev Arora and Boaz Barak.

Note: Do not send email to Professor Feigenbaum, who suffers from RSI. If you need to contact her, please go to her office hours, call her, or send email to her assistant Ms. Paige or to the TA.

Course 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. After Computer Science 365 or with permission of the instructor.

Pointers to the webpages for past iterations of CPSC 468/568 can be found on Professor Feigenbaum's "Courses" page.

Grading Scheme

  1. Undergraduates:
  2. Graduate students:

Note: There is no final exam during exam period at the end of the semester.


Lectures

  1. August 30, 2012: Course requirements; Introduction to complexity theory.
  2. September 4, 2012: The Turing-Machine model of computation, a demo of a Turing Machine recognizing a palindrome, running time, time constructibility, robustness of the Turing-Machine model, definitions of P, NP, and many-to-one, polynomial-time reductions.
  3. September 6, 2012: The Cook-Levin Theorem
  4. September 11, 2012: Simulation, universal TM, diagonalization, undecidability of the Halting Problem, Hierarchy Theorems, the existence of a function that is not time-constructible.
  5. September 13, 2012: Nondeterministic TMs, Oracle TMs, the Baker-Gill-Solovay Theorem.
  6. September 18, 2012: Space complexity, configuration graphs, PATH is in NL, and Savitch's Theorem.
  7. September 20, 2012: Logspace reductions, PATH is NL-complete, read-once certificates, and the Immerman-Szelepcsenyi Theorem.
  8. September 25, 2012: TQBF is PSPACE-complete. Alternating TMs.
  9. September 27, 2012: The Polynomial Hierarchy.
  10. October 2, 2012: Definition of P/poly. The Karp-Lipton Theorem.
  11. October 4, 2012: P is properly contained in P/poly. There are functions that have exponential circuit size. HW Problem 3.4.
  12. October 9, 2012: Probabilistic Turing Machines. Definitions of BPP, RP, coRP, and ZPP. BPP is contained in P/poly. ZPP = RP \cap coRP.
  13. October 11, 2012: [Exam1] [Solutions]
  14. October 16, 2012: The Sipser-Gacs Theorem. Definitions of interactive proof systems and Arthur-Merlin games. Graph non-isomorphism is in IP.
  15. October 18, 2012: Pairwise-independent hash-function families and the Goldwasser-Sipser lower-bound protocol.
  16. October 23, 2012: An interactive proof system for co-3SAT.
  17. November 1, 2012: An interactive proof system for TQBF.
  18. November 6, 2012: Definition of multiprover interactive proof systems. If the clique-number function can be 2-approximated in polynomial time, then EXP=NEXP.
  19. November 8, 2012: The USAT and Parity-SAT versions of the Valiant-Vazirani lemma.
  20. November 13, 2012: PH is contained in BPP^{Parity-SAT[1]}
  21. November 15, 2012: Toda's Theorem: PH is contained in P^{#SAT[1]}
  22. November 27, 2012: The 0-1 permanent, integer permanent, and #CYCLE problems
  23. November 29, 2012: The class PP, P^{PP} = P^{#P}, and elements of the proof that the permanent function is #P-complete.
  24. December 4, 2012: Communication complexity. Review for Exam2.
  25. December 6, 2012: [Exam2] [Solutions]

Homework

Note: All problems are from the textbook by Arora and Barak. The notation C.P means chapter number C, problem number P.

Advice: Make your best effort to do the problems yourself, i.e., without searching for relevant information online and without collaborating with your fellow students. This is the best way to learn the material (and to prepare for exams!). If you have questions, ask the TA. If, after making your best effort, you decide that you must work together in order to solve the problems, then please indicate on your HW paper whom you worked with.

  1. Due Sept. 18, 2012: 1.2, 1.5, 1.15, 2.13, 2.29, 2.30.
  2. Due Sept. 27, 2012: 3.3, 3.4, 4.4, 4.6, 4.8, 4.10.
  3. Due Oct. 9, 2012: 5.7, 5.9, 5.10, 6.3, 6.4, 6.9
  4. Due Nov. 1, 2012: 7.7, 7.9, 7.10, 8.1, 8.2, 8.3
  5. Due Nov. 15, 2012: 7.8, 8.5, 8.9, 8.10, 8.11, 8.12
  6. Due Dec. 4, 2012: 17.1, 17.2, 17.3, 17.4, 17.5

Reading Assignments

Note: All reading assignments are in the textbook by Arora and Barak unless otherwise indicated.

  1. August 30, 2012: Chapters 0 and 1
  2. September 13, 2012: Sections 2.4, 2.5, and 3.3
  3. September 20, 2012: Lemma 4.17
  4. October 2, 2012: Sections 6.1.2 and 6.2
  5. October 4, 2012: Appendix A.2
  6. October 18, 2012: Sections 7.5.3, 7.6, and 7.7
  7. November 27, 2012: Section 17.3