|
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, bounded-depth circuits, and
monotone circuits.
Administrative Information
Lectures: Mon 10:00-10:50 Wed 10:00-11:50 Room: 302
Professor: Sanjeev Arora - 307
CS Building - 258-3869 arora@cs.princeton.edu
Undergraduate Coordinator: Tina
McCoy - 410 CS Building - 258-1746 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 3-4 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, Cook-Levin 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,
Karp-Lipton). 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 (One-way functions and Goldreich-Levin Theorem)
Links: Oded Goldreich.
- Lecture 10+11 (Goldreich Levin contd, Playing poker
over the phone. Pseudorandom generation) Links: Andy Yao
- Lecture 12-13 (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 15-16 (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 Nisan-Kushilevitz.
- Lecture 21 (introduction to algebraic computation trees
and Blum-Shub-Smale 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)
