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.

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:

- 6 written HW assignments, each worth 10% of the course grade
- 2 in-class exams, each worth 20% of the course grade

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 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 ⊆ BPP^{parity-SAT[1]} |
Notes | |

Thursday, April 9 | PH ⊆ BPP^{parity-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 |

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

- Due Tuesday, Jan 27 Thursday, Jan 29, 2015[solutions]
- Problem 1.4
- Problem 1.5
- Problem 1.12
- Problem 2.13
- Problem 2.14
- Problem 2.32

- Due Tuesday, Feb 10, 2015 [solutions]
- Read Chapters 3 and 4 of your textbook.
- 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).
- Prove that there is an oracle A such that coNP
^{A}≠ NP^{A}and an oracle B such that coNP^{B}= NP^{B}. - Problem 4.4
- Problem 4.8
- 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.)

- Due Tuesday, Feb 24, 2015 [solutions]
- Problem 4.10
- Problem 5.7
- Problem 5.9
- Problem 6.3
- Problem 6.8
- Problem 6.9

- 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]
- Problem 7.7
- Problem 7.8
- Problem 7.10
- Problem 7.11
- Problem 8.2
- Problem 8.3

- Due Thursday, Apr 9, 2015. Make sure you read sections 8.4, 8.5, and 8.6 of your textbook before you begin.
[solutions]
- Problem 8.5
- Problem 8.9
- Problem 8.10
- Problem 8.11
- Problem 8.12

- 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]
- Problem 17.1
- Problem 17.2
- Problem 17.3
- Problem 17.4
- Problem 17.5

- Jan 20: Read Chapters 1 and 2 of the textbook. You may skim Sec. 2.4 and Subsecs. 2.7.5, 2.7.6, and 2.7.7.
- Feb 3: Read Chapters 3 and 4 of your textbook.
- Feb 17: Read the proofs of Theorem 6.6 and 6.18.
- Feb 24: Read appendix A.2 (Probability Theory) in your textbook.
- March 21: Sections 7.5.3, 7.6, and 7.7 of your textbook
- March 31: Sections 8.4, 8.5, and 8.6 of your textbook
- April 12: Sections 17.1, 17.2, and 17.3.1 of your textbook