Princeton University
|
Computer Science 522
|
Fall 2004 |
(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
Professor: Sanjeev Arora - 307 CS Building - 258-3869 arora@cs.princeton.edu
Graduate Coordinator: Melissa Lawson - 310 CS Building - 258-5387 mml@cs.princeton.edu
Text and readings: Chapters from a book that the instructor is writing. Occasional other readings.
SUBCRIBE TO THE CLASS MAILING LIST: Here
Homework
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.)