CS 278 -- Computational Complexity
Course given in Fall 2002
All lecture
notes in a single pdf file
[links] [notes]
Links, Interesting Papers, Quotes
People
P, NP, and all that stuff
Quotes
-
Once more, we have decreased the number of open questions in the field
- without, alas, increasing much the number of answers!
(C.H. Papadimitriou and M. Yannakakis, "Optimization, Approximation,
and Complexity Classes." JCSS 43:425-440, 1991.)
Lecture Notes
All notes from last year in a single ps file
(not completely revised, use at your own risk)
Tentative schedule:
-
[Lecture 1] 8/27 (revised 9/4) Diagonalization,
decision versus search problems, P, NP, reductions, NP-completeness.
-
[Lecture 2] 8/29 Space-bounded computations,
NL-completeness, Savitch's theorem.
-
[Lecture 3] 9/3 NL=coNL, introduction
to the polynomial hierarchy
-
[Lecture 4] 9/5 Non-uniform computations,
Karp-Lipton
-
[Lecture 5] 9/10 Probabilistic complexity
classes
-
[Lecture 6] 9/12 (revised 9/12)
Cheking polynomial identity
-
[Lecture 7] 9/17 (revised 9/18) Valiant-Vazirani
-
[Lecture 8] 9/19 (posted 9/18) #P and
Approximate counting
-
[Lecture 9] 9/24 (posted 9/25) Average-case
complexity (random self-reduction for the Permanent via polynomial reconstruction)
-
[Lecture 10] 9/26 (revised 9/26) Average-case
complexity (more polynomial reconstruction)
-
[Lecture 11] 10/1 (posted 10/1) Average-case
complexity (hardness of problems in EXP and PSPACE, List-decoding)
-
[Lecture 12] 10/3 (posted 10/3) Average-case
complexity (XOR Lemma)
-
[Lecture 13] 10/8 (posted 10/3) Average-case
complexity (Levin's theory)
-
[Lecture 14] 10/10 (revised 10/10) Introduction
to interactive proofs
-
[Lecture 15] 10/15 (posted 10/9) IP=PSPACE
-
[Lecture 16] 10/17 PCP and hardness of
approximation
-
[Lecture 17] 10/22 (posted 11/4) More
hardness of approximation, parallel repetition, efficient composition
-
[Lecture 18] 10/24 Discussion of the midterm, more on parallel repetition
and composition
-
[Lecture 19] 10/29 (posted 11/12) Fourier
analysis, linearity testing
-
[Lecture 20] 10/31 (posted 11/4) Hastad's
verifier
-
[Lecture 21] 11/5 (posted 12/3) Parity
is not in AC0: proof with polynomials
-
[Lecture 22] 11/7 (posted 12/3)
Parity is not in AC0: proof with random restrictions
-
[Lecture 23] 11/12 (posted 11/25) Proof
complexity, resolution, width
-
[Lecture 24] 11/14 (posted 11/25) Width
lower bounds
-
11/19 FOCS, no lecture
-
[Lecture 25] 11/21 (posted 11/20) Pseudorandomness
and derandomization
-
[Lecture 26] 11/26 (posted 11/25) Nisan-Wigderson
-
11/28 no lecture
-
[Lecture 27] 12/3 (posted 11/25) Extractors,
error-correcting codes
-
[Lecture 28] 12/5 Extractors and pseudorandom generators from polynomials