Princeton University Computer Science Dept.

Computer Science 594 Advanced Topics in Algorithms: Algorithms & Complexity Sanjeev Arora

Spring 1999

Directory
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 arora@cs.princeton.edu

First meeting: Wednesday, Feb. 3.

Tentative list of topics (subject to change):

• Definitions of complexity classes: P, NP, PSPACE, PH, BPP, P/poly etc and their interrelationships.
• Randomized computation: BPP, RP, Random self-reducibility, interactive proofs
• Algebraic methods in complexity theory: IP=PSPACE and NP=PCP(log n, 1)
• Cryptography: one-way functions, pseudorandom generators, and hardness vs randomness.
• Circuit complexity as an approach to separate P from NP.
• Proof theory and lowerbounds for proof sizes. Relationship to independence of P vs NP question from logical theory. Proof systems based on Hilbert's nullstellensatz.
• Miscellaneous topics: Hardness of computing approximate solutions to NP-hard problems; Studying whether or not NP-complete problems have subexponential algorithms, etc.