CPSC468/568: Computational Complexity (Fall 2012)

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.

Grading Scheme

1. Undergraduates:
   • 6 written HW assignments, each worth 10% of the course grade
   • 2 in-class exams, each worth 20% of the course grade
2. Graduate students:
   • 6 written HW assignments, each worth 9% of the course grade
   • 2 in-class exams, each worth 20% of the course grade
   • Lecture-note preparation, worth 6% of the course grade

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: Exam 1
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

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