CPSC 468/568: Computational Complexity (Spring 2016)

Course Details

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.

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

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.

Tentative schedule

# 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


  1. Due Thursday, 04 February, 2016 [link]
  2. Due Thursday, 18 February, 2016 [link]
  3. Due Thursday, 03 March, 2016 [link]
  4. Due Thursday, 31 March, 2016 [link]
  5. Due Tuesday, 12 April, 2016 [link]
  6. Due Tuesday, 26 April, 2016 [link]

Reading Assignments