
Computer Science 522
Computational Complexity
Sanjeev Arora

Spring 2001

Directory
General Information  Assignments  What's New?
Course Summary
Introduction to research in computational complexity theory. Computational models:
nondeterministic, alternating, and probabilistic machines. Boolean circuits. Complexity
classes associated with these models: NP, Polynomial hierarchy, BPP, P/poly, etc. Complete
problems. Interactive proof systems and probabilistically checkable proofs: IP=PSPACE and
NP=PCP (log n, l). Definitions of randomness. Pseudorandomness and derandomizations. Lower
bounds for concrete models such as algebraic decision trees, boundeddepth circuits, and
monotone circuits.
Administrative Information
Lectures: Mon 10:0010:50 Wed 10:0011:50 Room: 302
Professor: Sanjeev Arora  307
CS Building  2583869 arora@cs.princeton.edu
Undergraduate Coordinator: Tina
McCoy  410 CS Building  2581746 tmmccoy@cs.princeton.edu
Teaching Assistants: None
The course will be structured somewhat differently from last year's offering and
students who took last year's course will still get to see a lot of new topics. There will
be 34 assignments during the semester, and a course project. Students taking the course
for credit will need to act as "scribes" for two lectures each, and to write up
their notes in latex. The latex style files etc. are here.
Scribes should strive for good mathematical style. A
few pages from Mathematical Writing by by Knuth, Larrabee, and Roberts
provide some good hints.
LECTURE NOTES
(please also see the web site for a sister
course at Berkeley)
 Lecture 1 (P, NP, CookLevin Theorem, General musings)
Interesting links: Steve
Cook and Leonid Levin.
 Lecture 2 (Space bounded computation, Savitch's Thm,
Immerman Szlepcsenyi, TQBF). Links: Walter
Savitch, N. Immerman.
 Lecture 3 (Diagonalization and its limits) Links: Hartmanis.
 Lecture 4 (Polynomial hierarchy) Links: Meyer and Stockmeyer, who first defined
polynomial hierarchy.
 Lecture 5 (Circuits, Nonuniform computation,
KarpLipton). Links: Karp and Lipton.
 Lecture 6 (Randomized computation) Links: Sipser. "How to recycle random bits"
by Impagliazzo and Zuckerman.
 Lecture 7 (Counting classes, #P, Permanent) Links: Valiant.
 Lecture 8 (Toda's Theorem) Links: S. Toda, and his prize citation
 Lecture 9 (Oneway functions and GoldreichLevin Theorem)
Links: Oded Goldreich.
 Lecture 10+11 (Goldreich Levin contd, Playing poker
over the phone. Pseudorandom generation) Links: Andy Yao
 Lecture 1213 (Interactive proofs, graph
nonisomorphism, private coin vs public coins, IP=PSPACE) Links: Goedel Prize citation
for invention of interactive proofs.
 Lecture 14 (program checking/correcting, linear functions, and their use in PCPs). Link:
Manuel Blum. Handout: Linearity testing.
 Lecture 1516 (PCP Theorem and its use in proving hardness of approximation)
 Lecture 17 (Decision tree complexity; certificate
complexity, randomized complexity and Yao's lemma) Joke Link: Decision tree homepage
 Lecture 18 (An introduction to Communication complexity)
 Lecture 19 (Introduction to circuit lower bounds,
Håstad Switching Lemma) Link: Johan Håstad
 Lecture 20 (circuit lower bounds using multiparty
communication complexity ) Links: Babai,
Nisan, Szegedy and a proof
of their lowerbound form NisanKushilevitz.
 Lecture 21 (introduction to algebraic computation trees
and BlumShubSmale model) Link: Book on BSS model
 Lecture 22 (natural proofs: why existing methods for
proving circuit lowerbounds may not generalize to show P != NP) Links: Razborov and Rudich.
 Lecture 23 (quantum computation and Shor's algorithm)
Link: Peter Shor.
Scanned handwritten notes
HOMEWORK
Homework 1 (due Monday Feb 26)
Homework 2 (due Wed March 14)
Homework 3 (due Wed April 4)
Homework 4 (due Wed April 25)
Final homework/course project (due May 10)