CS 278 -- Computational Complexity
Course given in Spring 2001
All lecture notes in a single ps file
[links] [notes]
Links, Interesting Papers, Quotes
our twin
course at Princeton
People
P, NP, and all that stuff
Quotes
On the nature of complexity-theoretic results
-
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.)
On oracles
-
I do believe it
Against an oracle
(Line spoken by Fernando in "The
Tempest," by William Shakespeare)
-
This is as strange a maze as e'er men trod
And there is in this business more than nature
Was ever conduct of: some oracle
Must rectify our knowledge
(Line spoken by Alonso in "The
Tempest," by William Shakespeare)
On efficiency
-
This administration is doing everything we can to end the stalemate
in an efficient way. We're making the right decisions to bring the solution
to an end.
(President G.W.
Bush, April 10, 2001)
More quotes
Lecture Notes
All notes in a single ps file
-
[Lecture
1] (preliminary version posted 1/21) decision problems, search problems,
P, NP, reductions, NP-completeness
-
[Lecture
2] (preliminary version posted 1/23) NP-completeness of SAT and 3SAT
-
[Lecture
3] (posted 1/28) NP-completeness of Independent Set, introduction to
space-bounded classes.
-
[Lecture
4] (posted 2/12) NL-completeness, Savitch
-
[Lecture
5] (posted 2/12) NL=coNL, polynomial hierarchy
-
[Lecture
6] (posted 2/12) Circuits
-
[Lecture
7] (posted 3/18) Probabilistic complexity classes
-
[Lecture
8] (posted 3/18) Probabilistic algorithms
-
[Lecture
9] (posted 3/18) BPP versus PH, and counting problems
-
[Lecture
10] (posted 3/18) Approximate counting
-
[Lecture
11] (posted 3/18) Valiant-Vazirani, introduction to cryptography
-
[Lecture
12] (posted 3/18) One-way function, hard-core predicates, pseudorandom
generators
-
[Lecture
13] (posted 4/5) Pseudorandom generators, pseudorandom functions
-
[Lecture
14] (posted 4/5)Error-correcting codes and Goldreich-Levin
-
[Lecture 15] (posted 5/2) Levin's average-case
complexity theory
-
[Lecture
16] (posted 4/5) Average-case complexity of the permanent
-
[Lecture 17] (posted 5/2) Introduction
to interactive proofs
-
[Lecture 18] (posted 5/2) IP=PSPACE
-
[Lecture 19] (posted 5/2) IP=PSPACE
-
[Lecture 20] (posted 5/2) PCP and hardness
of approximation
-
[Lecture 21] (posted 6/12) NP=PCP[log
n, polylog n]
-
[Lecture 22] (posted 6/12) NP=PCP[log
n, polylog n]
-
[Lecture 23] (posted 5/2) parallelization
-
[Lecture 24] (posted 6/12) parallelization
-
[Lecture 25] (posted 6/12) NP in PCP[poly(n),O(1)]
(april 20)
-
[Lecture 26] (posted 6/12) Pseudorandomness
and derandomization (april 23)
-
[Lecture 27] (posted 6/12) Nisan-Wigderson
(april 25)
-
[Lecture 28] (posted 6/12) Extractors
(april 30)
-
[Lecture 29] (posted 6/12) Extractors,
error-correcting codes, and worst-case to average-case reductions (May
2)
-
[Lecture 30] (posted 6/12) Miltersen-Vinodchandran
(may 7)