Princeton University
Computer Science Department

Computer Science 522
Computational Complexity Theory
Sanjeev Arora

Fall 2004

Course Summary

(From course catalog:) 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.

The focus this year will be on research from the past decade or so (with enough introductory material to make it accessible to undergraduates): interactive proofs and probabilistically checkable proofs, new definition of NP, computational pseudorandomness, proof complexity, and some cryptography. Avi Wigderson (professor at Institute for Advanced Study) will give several guest lectures.

The mix of students will influence the syllabus and the pace of the course. There will be 4-5 problem sets and a take home


Administrative Information

Lectures: TTh 1330-1450  in Room Friend 004.

Professor: Sanjeev Arora - 307 CS Building - 258-3869

Graduate Coordinator: Melissa Lawson - 310 CS Building - 258-5387

Text and readings: Chapters from a book that the instructor is writing. Occasional other readings.



HW 1: Chapter 2:Qs 3, 6; Chapter 3: Qs 4, 6; Chapter 4: Qs 4, 6, 7.

HW 2: pdf version.

HW 3 pdf version

HW4 pdf

FINAL: (Do not read it until you are ready to work on it):

The relevant instruction: Finish the test within 96 hours after first reading it.
You can consult any notes/handouts from this class as well as the text.
Feel free to quote, without proof, any results from class or the text.
You cannot consult any other source or person in any way.
 Due back on Jan 11 in my office.

Readings, Resources.

Salil Vadhan's course on pseudorandomness. (Has online scribe notes.)