Computer Science 594
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 undergrad-level knowledge of algorithms and NP-completeness.)
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 - 258-3869 firstname.lastname@example.org
First meeting: Wednesday, Feb. 3.
Tentative list of topics (subject to change):