Deprecated : The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
CS 278 -- Computational Complexity
Course given in Fall 2002
All lecture
notes in a single pdf file
[links] [notes]
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!
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