|
Computer Science 522
Computational Complexity
Andy Yao |
Spring 2000 |
Directory
General Information |
Assignments |
Solutions |
Handouts |
Final Exam |
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: TTh 1:30-2:50pm, Room: 302 CS Building
Professor: Andy Yao -
321 CS Building - 258-5182
yao@cs.princeton.edu
Undergraduate Coordinator:
Tina McCoy -
410 CS Building - 258-1746
tmhill@cs.princeton.edu
Teaching Assistants: