Princeton University
Computer Science Dept.

Computer Science 594
Advanced Topics in Algorithms: Algorithms & Complexity

Sanjeev Arora

Spring 1999

General Information | Assignments/Handouts |

First meeting: Feb 3

Course Summary

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.

Administrative Information

Lectures: MW 1:30-2:50, Room: 301 (Could be changed if many in the class request it)

Professor: Sanjeev Arora - 307 CS Building - 258-3869

First meeting: Wednesday, Feb. 3.

Tentative list of topics (subject to change):