Princeton University
Computer Science Department

Computer Science 522
Computational Complexity

Sanjeev Arora

Spring 2001

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

Undergraduate Coordinator: Tina McCoy - 410 CS Building - 258-1746

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.


(please also see the web site for a sister course at Berkeley)

Scanned handwritten notes


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)