Princeton University

Computer Science 594


Directory
General Information  Assignments/Handouts 
First meeting: Feb 3
This course will start by introducing basic ideas of computational complexity theory, and then move to developments of the past decade, and especially the past three years. I will give most of the lectures. There will be biweekly problem sets. Students will also be expected to read at least one recent paper and present it in class.
Prerequisites: COS 423 or 487 or equivalent. (Realistically, some mathematical skill and undergradlevel knowledge of algorithms and NPcompleteness.)
Auditing: Auditors are welcome but are strongly urged to do the problem sets in order to keep up with the pace of the course.
Text: There is no text. Papadimitriou's book Computational Complexity covers some of the topics but is quite basic. Some lecture notes are available on the handouts page.
Professor: Sanjeev Arora  307 CS Building  2583869 arora@cs.princeton.edu
First meeting: Wednesday, Feb. 3.
Tentative list of topics (subject to change):