Time: TTh, 2:30 p.m. - 3:45 p.m.
Location: AKW 000
Instructor: Joan Feigenbaum
Professor Feigenbaum's Office Hours: By appointment (see Judi Paige). Regular hours TBA.
Professor Feigenbaum's Assistant: Judi Paige (AKW 507A, Judi.Paige@yale.edu, 203-436-1267)
TA: Debayan Gupta (AKW 503, debayan.gupta@yale.edu)
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
Boaz Barak.
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.
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.
| # | Date | Description | Downloads |
|---|---|---|---|
| Tuesday, January 19 | Course requirements and introduction to complexity theory | Slides | |
| Thursday, January 21 | Turing Machine model of computation, nondeterminism, and the classes P and NP | ||
| Tuesday, January 26 | The Cook-Levin Theorem: SAT is NP-Complete | Notes | |
| Thursday, January 28 | Undecidability and the Halting Problem | Notes | |
| Tuesday, February 2 | Time-Hierarchy Theorems | Notes | |
| Thursday, February 4 | The Baker-Gill-Solovay Theorem. HW1 due. | Notes | |
| Tuesday, February 9 | Space complexity, Savitch's Theorem, and PATH is NL-complete | Notes | |
| Thursday, February 11 | The Immerman-Szelepcsényi theorem (NL = coNL) | Notes | |
| Tuesday, February 16 | TQBF is PSPACE-complete | Notes | |
| Thursday, February 18 | The Polynomial Hierarchy. Alternating Turing Machines. HW2 due. | ||
| Tuesday, February 23 | Boolean circuits, the class P/poly, and the Karp-Lipton Theorem | Notes | |
| Thursday, February 25 | Three Results about Circuit Size, including Adleman's Theorem (BPP is contained in P/poly) | Notes | |
| Tuesday, March 1 | Two Results about Probabilistic Polynomial Time, including the Sipser-Gacs Theorem (BPP is contained in Σ2P ∩ Π2P) | Notes | |
| Thursday, March 3 | Review for Exam 1. HW3 due. | ||
| Tuesday, March 8 | Exam 1 in class | ||
| Thursday, March 10 | Return corrected HWs and Exams, together with mid-term course grades | ||
| Friday, March 11 | Drop date | ||
| Tuesday, March 29 | Pairwise-Independent Hash-Function Families and the Goldwasser-Sipser Lower-Bound Protocol | Notes | |
| Thursday, March 31 | Arithmetization of Boolean Formulas, and an Interactive Proof Systems for co3SAT. HW4 due. | Notes | |
| Tuesday, April 5 | An Interactive Proof System for TQBF | Notes | |
| Thursday, April 7 | MIP = NEXP and the Nonapproximability of CLIQUE | Notes | |
| Tuesday, April 12 | Valiant-Vazirani: NP ⊆ BPPparity-SAT[1]. HW5 due. | Notes | |
| Thursday, April 14 | PH ⊆ BPPparity-SAT[1] | Notes | |
| Tuesday, April 19 | Toda: PH ⊆ P#SAT[1] | Notes | |
| Tuesday, April 26 | Review for Exam 2. HW6 due. | ||
| Thursday, April 28 | Exam 2 in class |