This is a draft of a textbook on computational complexity theory.
It is intended as a
text for an advanced undergraduate course or introductory graduate course, or
as a reference for researchers and students in computer science and allied
fields such as mathematics and physics. We plan to keep this rough draft on the
web, even after the book is published,
as a resource for teachers and students from developing countries.
Update: We have pushed back the publication date, and now plan to
submit the book by May 2007,
the expected publication date is January 2008.
We would be grateful for comments, especially of the following kind:
Places in the book that are
difficult for non-specialists, e.g., due to inadequate explanations or use
of jargon.
Incorrect proofs or
calculations.
Topics you normally teach but
are missing (please check the table of contents for topics we still plan
to add).
Places where, in your
experience, students get confused and need additional explanations or a
worked-out exercise.
Missing or incorrect
references. (We are working on the references and historical notes, but
would like to know about any inaccuracies, for which we apologize in
advance.)
We are grateful for the comments we already received, which we are
still working on implementing. Please send any additional comments to
Diagonalization
Time, Non-deterministic time, and space hierarchy theorems, Ladner's
theorem, oracle machines and proof that relativized methods can't resolve
P vs. NP.
Space
Complexity PSPACE, L, NL. TQBF is PSPACE complete, Savitch's
Theorem, Path is NL-complete, NL=coNL.
The
polynomial hierarchy and alternations. Definitions of PH via
alternating quantifiers and alternating machines, conjecture it doesn't
collapse, time-space tradeoffs for SAT.
Circuits.
Boolean circuits and the class Ppoly. Definition using advice. Karp-Lipton
theorem. Non-uniform hierarchy theorem. circuit-satisfiability and
alternative proof for Cook-Levin theorem.
Randomized
Computation BPP, RP, coRP, ZPP. Examples of probabilistic
algorithms. Error reduction via repetition. BPP in P/poly and PH.
Randomized reductions, randomized logspace algorithms. Second eigenvalue and analysis of
random walks.
Cryptography
One-way functions, pseudorandom generators: prediction vs. distinguishing.
Goldreich-Levin theorem. Zero knowledge and ZK proof for graph
isomorphism. Overview of advanced topics in cryptography.
Part II: Lower bounds for concrete computational
models
Decision
Trees certificate complexity, randomized complexity, sorting
lowerbounds
Communication
Complexity Lowerbound methods (fooling set, rank, tiling,
discrepancy), multiparty communication complexity
Circuit
lowerbounds. Hastad switching lemma, lowerbounds for monotone
circuits, frontier of circuit lowerbounds, approaches using communication
complexity.
Derandomization,
Expanders and Extractors Pseudorandom generators from average-case hardness
- the NW generators. Extractors from hash functions. Zig-zag construction of expanders,
reingold's deterministic logspace algorithm for undirected connectivity. Trevisan's extractor
from NW.
Hardness
amplification and error correcting codes Worst-case to average
case reduction. Error correcting codes. Pseudoarndom generators from
worst-case assumptions. List decoding and its use for hardness
amplification.
PCP
and hardness of approximation. NP in PCP(poly,1). The PCP theorem
(Dinur's proof). Independent set is hard to approximate within a
polynomial factor.
More
PCP Theorems and the Fourier Transform Technique Fourier transforms
over GF(2)^n. Analysis of linearity testing. Hastad's 3-query PCP, 3SAT is
hard to 7/8+epsilon approximate. Learning fourier coefficients
(Goldreich-Levin / Kushilevits-Mansour)
Quantum
Computation Quantum computation and the class QBP. Shor's
factoring algorithm.