CPSC468/568: Computational Complexity
Assignments | Course Information
| Lectures | Homework
- January 18, 2007:
In the (online) Arora-Barak book, read sections 1.3, 1.4, 1.5, and 1.A
carefully. Also skim the Introduction and the rest of Chapter 1.
- Jan 22, 2007:
In Arora-Barak, read Sections 2.4, 2.5, 2.6, and 2.7
carefully. Sections 2.1, 2.2, and 2.3 will be covered in class, but you should
skim those as well.
- Jan 30, 2007: Read chapter 3 of Arora-Barak; Sections 3.3 and 3.4
should be read most carefully.
- Feb 6, 2007: Read chapter 4 of Arora-Barak, paying special attention
to sections 4.3 (just before Savitch's theorem) and 4.3.2 (on PSPACE and
games), and the proofs of Theorem 4.11 and Lemma 5.15.
- Feb 15, 2007: Read chapter 6 of Arora-Barak.
- Mar 27, 2007: Read Chapter 8 of Arora-Barak.
- 7. Apr 10, 2007: Scrutinize the proof that 0-1 PERM is #P-complete (in
Chapter 9 of Arora-Barak) and review the proof of the Cook-Levin Theorem (in
Chapter 2 of Arora-Barak).
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.
T/Th, 1:00 - 2:15 p.m., AKW 500
Further details are available in the slides for the first lecture. [PPT]
Note: Professor Feigenbaum suffers from Repetitive Strain Injury
and cannot handle large amounts of email. Do NOT send her email about
CPSC468/568; instead, please contact her by phone, through the TA, or
through her assistant Judi Paige (Tel: 203-436-1267, email: Judi.Paige@yale.edu).
||Tuesday 4-5PM; Thursday 9-10AM
||Tuesday 930-1030am, Friday 10-11am
- Jan 16, 2007: Course outline, introduction [PPT]
- Jan 18, 2007: Introduction to Complexity Classes [PPT]
- Jan 23, 2007: Robustness of the Turing-Machine model, many-to-one
polynomial-time reductions, P, NP, and reduction from SAT to 3SAT (from [AB,
chapters 1 and 2])
- Jan 25, 2007: Proof that SAT is NP-Complete (from [AB, chapter 2])
- Jan 30, 2007: Diagonalization, basic hierarchy theorems, proofs that
relativize vs. those that don't, statement and proof of the Baker-Gill-Solovay
Theorem, statement of Ladner's Theorem (from [AB], chapter 3)
- Feb 1, 2007: Space complexity; the classes PSPACE, L, and NL; statement
and proof that PATH is in NL; introduction to the PSPACE-complete problem TQBF
(from [AB], chapter 4)
- Feb 6, 2007: PATH is NL-complete, "read-once-certificates" definition of
NL, Savitch's Theorem (from [AB, chapter 4])
- Feb 8, 2007: The Immerman-Szlepcsenyi Theorem, review of the essentials of
space-complexity (from [AB, chapter 4]), introduction to the Polynomial
Hierarchy (from [AB, chapter 5]).
- Feb 13, 2007: Proofs of Berman's Theorem and Rice's Theorem (from
solutions to Homework 1).
- Feb 15, 2007: Definition of alternating Turing Machines and ATIME(T(n)),
three equivalent definitions of the PH (from [AB, chapter 5]); introduction to
circuit complexity and P/poly (from [AB, chapter 6]).
- Feb 20, 2007: Turing machines that take advice, the Karp-Lipton Theorem,
logspace-uniform circuit families, and the complexity classes NC and AC (from
[AB, chapter 6]).
- Feb 22, 2007: Probabilistic Turing machines; the complexity classes RP,
co-RP, ZPP, and BPP; applying the Chernoff bound on the tails of the binomial
distribution; BPP is contained in P/poly (from [AB, chapter 7]).
- Feb 27, 2007: Review for Exam 1
- Mar 1, 2007: Exam 1
- Mar 6, 2007: Review of Question 4 from Exam 1. Proof that BPP is
contained in Sigma_2^P and in Pi_2^P (from [AB, Chapter 7]).
- Mar 8, 2007: Space-bounded, probabilistic computation; the complexity
classes RL, coRL, BPL, and SL; PATH is in SL (from [AB, Chapter7]); the
complexity class IP and the proof that GNI (graph non-isomorphism) is in IP
(from [AB, Chapter 8]).
- Mar 27, 2007: Pairwise-independent hash-function collections;
Goldwasser-Sipser Set Lowerbound proofs (from [AB, Chapter 8]).
Mar 29, 2007: Public coins are as powerful as private coins in interactive
proof systems; specifically, IP[k] is contained in AM[k+2] (from a paper by
Goldwasser and Sipser that was distributed in class).
- Apr 3, 2007: IP = PSPACE. [PPT]
- Apr 5, 2007: Connection between MIP=NEXP and nonapproximability of CLIQUE;
introduction to the complexity class #P.
- Apr 10, 2007: Interpretations of 0-1 PERM in terms of perfect matchings
and integer PERM in terms of cycle covers, proof that 0-1 PERM is #P-complete
(from [AB, Chapter 9]).
- Apr 12, 2007: Valiant-Vazirani theorem (from [AB, Chapter 9]).
- Apr 17, 2007: Toda's Theorem (from [AB, Chapter 9]).
- Apr 19, 2007: Communication complexity; fooling sets; linear lower bound on the communication complexity of set disjointness; relationship with streaming space complexity.
- Apr 24, 2007: Review for Exam 2.
- Apr 26, 2007: Exam 2 [PDF] [Solutions]
- HW1 (due Feb 1): Problems 1.1, 1.8, 1.12, 1.15, 2.3, 2.4, 2.7,
2.13, 2.17, and 2.21.
- HW2 (due Feb 13): Problems 3.2, 3.4, 3.6, 4.1, 4.2, 4.4, 4.5, 4.6,
- HW3 (due Feb 22): Problems 5.4, 5.8, 6.9, 6.11, 6.13.
- HW4 (due April 10):
Problems 8.1, 8.2, 8.9, 8.10, 8.11, 9.1, and 9.5.
- HW5 (due April 22): 9.2, 9.3, 12.2., 12.3, 12.5, 12.7, 12.8.