Princeton University

Computer Science 522


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.
Professor: Sanjeev Arora  307 CS Building  2583869 arora@cs.princeton.edu
Graduate Coordinator: Melissa Lawson  310 CS Building  2585387 mml@cs.princeton.edu
Scribe notes: Every student taking or auditing the course is asked to write
scribe notes for a
lecture using the latex system. Relevant style files appear here.
Scribes should strive for good
mathematical style. A few pages from Mathematical
Writing by by Knuth, Larrabee, and Roberts provide some good hints.
Study material:
Lecture topics:
The first 12 or so lectures will be similar to the ones in the Spring 2000 offering of this course. After that the topics will often be a little different.
Handouts:
Homework 1 (due Feb 26)
Homework 2 (due March 26)
Homework 3 (due April 18).
Homework 4 (due May 2)
Edited lecture notes:
SCRIBE NOTES