CPSC 468/568: Computational Complexity (Spring 2015)

Course Details

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, 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.

Lectures

# Date Description Downloads
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[1] Notes
Thursday, April 9 PH ⊆ BPPparity-SAT[1]. Fifth HW Assignment Due. Notes
Tuesday, April 14 Toda: PH ⊆ P#SAT[1] 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

Homework

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

  1. Due Tuesday, Jan 27 Thursday, Jan 29, 2015[solutions]
    1. Problem 1.4
    2. Problem 1.5
    3. Problem 1.12
    4. Problem 2.13
    5. Problem 2.14
    6. Problem 2.32
  2. Due Tuesday, Feb 10, 2015 [solutions]
    1. Read Chapters 3 and 4 of your textbook.
    2. Fill in the holes (boldfaced "WHY"s) in the posted proof of the Baker-Gill-Solovay Theorem (notes for Lecture 5, which was cancelled because of the blizzard).
    3. Prove that there is an oracle A such that coNPA ≠ NPA and an oracle B such that coNPB = NPB .
    4. Problem 4.4
    5. Problem 4.8
    6. Problem 4.10 (05-Feb-2015: This problem has been cancelled. At least one problem about PSPACE-completeness will be included on HW 3 instead.)
  3. Due Tuesday, Feb 24, 2015 [solutions]
    1. Problem 4.10
    2. Problem 5.7
    3. Problem 5.9
    4. Problem 6.3
    5. Problem 6.8
    6. Problem 6.9
  4. Due Tuesday, Mar 31, 2015. This HW is longer and harder than previous ones. Make sure you read sections 7.5.3, 7.6, and 7.7 of your textbook before you begin. [solutions]
    1. Problem 7.7
    2. Problem 7.8
    3. Problem 7.10
    4. Problem 7.11
    5. Problem 8.2
    6. Problem 8.3
  5. Due Thursday, Apr 9, 2015. Make sure you read sections 8.4, 8.5, and 8.6 of your textbook before you begin. [solutions]
    1. Problem 8.5
    2. Problem 8.9
    3. Problem 8.10
    4. Problem 8.11
    5. Problem 8.12
  6. Due Tuesday, Apr 21, 2015. Be sure to do the April 12 reading assignment before you begin, because it is needed for these problems. [solutions]
    1. Problem 17.1
    2. Problem 17.2
    3. Problem 17.3
    4. Problem 17.4
    5. Problem 17.5

Reading Assignments