Time: TTh, 2:30 p.m. - 3:45 p.m.
Location: AKW 000
Instructor: Joan Feigenbaum
Professor Feigenbaum's Office Hours: Thursdays 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: Debayan Gupta (AKW 503, firstname.lastname@example.org)
TA's Office Hours: Tuesdays and Thursdays 4:00 p.m. to 5:00 p.m. in AKW 503 or by appointment
Textbook: Computational Complexity, A Modern
Approach, by Sanjeev Arora and
The textbook is available online on Yale Orbis (Orbis page, online textbook).
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.
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.
Undergraduates will have:
Graduate students will also have to prepare lecture notes and/or do an in-class presentation.
The late penalty for HW assignments is 5% per day for at most 7 days, after which solutions are posted and HWs not yet turned in receive a grade of zero. Try to do the HW on your own. If you work in a group to solve a HW problem, identify the group members on your HW paper. If you use any sources except the textbook and classnotes, identify them.
There will be NO final exam during exam week.
|Tuesday, January 13||Course requirements and introduction to complexity theory||Slides|
|Thursday, January 15||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.||Notes Palindrome TM animation|
|Tuesday, January 20||The Cook-Levin Theorem||Notes|
|Thursday, January 22||Undecidability, diagonalization, time-hierarchy theorems, Gap Theorem||Notes|
|Tuesday, January 27||The Baker-Gill-Solovay Theorem.||Notes|
|Thursday, January 29||Space complexity, configuration graphs, Savitch's theorem. First HW Assignment Due (was originally due on Tuesday, January 27)||Notes|
|Tuesday, February 3||L, NL, logspace reductions, and PATH is NL-complete||Notes|
|Thursday, February 5||Immerman-Szelepcsényi theorem (NL = coNL)||Notes|
|Tuesday, February 10||TQBF is PSPACE-complete. Second HW Assignment Due.||Notes|
|Thursday, February 12||Alternating Turing Machines, three definitions of the Polynomial Hierarchy given in Chapter 5 of your textbook, and Theorem 5.12. Because this material is presented clearly and succinctly in the book, no lecture notes are provided.|
|Tuesday, February 17||Boolean circuits, the class P/poly, and the Karp-Lipton Theorem.||Notes|
|Thursday, February 19||Turing Machines that take advice. Shannon's basic lower bound on circuit size. BPP is contained in P/poly.||Notes|
|Tuesday, February 24||The Sipser-Gacs Theorem. Third HW Assignment Due.||Notes|
|Thursday, February 26||First In-Class Exam||Exam 1 Exam 1 Solutions|
|Tuesday, March 3||ZPP, Interactive Proofs and Arthur-Merlin games, and pairwise-independent hash functions||Notes|
|Thursday, March 5||Goldwasser-Sipser Lower Bound Protocol||Notes|
|Friday, March 6||Fall Semester Drop Date|
|Tuesday, March 24||Arithmetization, Interactive proof for co3SAT||Notes|
|Thursday, March 26||Interactive proof system for TQBF||Notes|
|Tuesday, March 31||Review of IP for TQBF, Goldwasser-Sipser IP[Q] ⊆ AM[Q+2] (first half)|
|Thursday, April 2||Goldwasser-Sipser: IP[Q] ⊆ AM[Q+2] (second half)|
|Tuesday, April 7||Valiant-Vazirani: NP ⊆ BPPparity-SAT||Notes|
|Thursday, April 9||PH ⊆ BPPparity-SAT. Fifth HW Assignment Due.||Notes|
|Tuesday, April 14||Toda: PH ⊆ P#SAT||Notes|
|Thursday, April 16||MIP and the nonapproximability of the clique-number function. Review of the relationships among complexity classes that have been covered this semester.||Notes|
|Tuesday, April 21||Sixth HW Assignment Due|
|Thursday, April 23||Second In-Class Exam|
All problems are from the textbook by Arora and Barak, unless otherwise stated. The notation C.P means chapter number C, problem number P.