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, bounded-depth circuits, and monotone circuits.
Professor: Sanjeev Arora - 307 CS Building - 258-3869 firstname.lastname@example.org
Graduate Coordinator: Melissa Lawson - 310 CS Building - 258-5387 email@example.com
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.
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.
Homework 1 (due Feb 26)
Homework 2 (due March 26)
Homework 3 (due April 18).
Homework 4 (due May 2)
Edited lecture notes: