|
Computer Science 522
Computational Complexity
Amit Sahai |
Spring 2002 |
Directory
General Information
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: M 3-4:20 (Room 402), W 11:00-12:20 (Room 103)
Professor: Amit Sahai -
406 CS Building - 258-0255
sahai@cs.princeton.edu
Graduate Coordinator:
Melissa Lawson -
310 CS Building - 258-5387
mml@cs.princeton.edu
Teaching Assistants:
None
Homework 1: Due Feb 25
Homework 2: Due March 27
Homework 3: Due April 16