Princeton University
Computer Science Department

Computer Science 522
Computational Complexity Theory
Sanjeev Arora

Spring 2003

Course Summary

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.

Administrative Information

Lectures: Wed 11-12:20 and Friday 10:30-11:50 in Room 102. FIRST CLASS ON WED FEBRUARY 5.

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

Scribe notes:  Every student taking or auditing the course is asked to write scribe notes for a
lecture using the latex system. Relevant style files appear here. Scribes should strive for good
mathematical style.  A few pages from Mathematical Writing by by Knuth, Larrabee, and Roberts provide some good hints.

Study material:

  1. Edited scribe notes from the Spring 2000 offering.
  2. Dan Spielman's lecture notes are here.
  3. Luca Trevisan's lecture notes are here.

Lecture topics:

The first 12 or so lectures will be similar to the ones in the Spring 2000 offering of this course. After that the topics will often be a little different.

  1. P vs NP, and introduction.
  2. Space complexity.
  3. Diagonalization and why it can't resolve P vs NP
  4. Polynomial hierarchy
  5. Circuits
  6. Randomized computation
  7. Counting classes
  8. Toda's theorem.
  9. Random self-reducibility, average case hardness "what is a random string"
  10. Intro to crypto, Goldreich Levin
  11. Interactive proofs; Private coins versus private coins
  12. Interactive proofs for #P; program checking.
  13. PCP Theorem; Introduction
  14. PCP Theorem: Algebraic satisfiability and the first verifier
  15. PCP Theorem: Aggregating queries.
  16. PCP Theorem: Constant bit verifier.
  17. Fourier transform technique, Linearity test, longcode test.
  18. Sketch of Hastad's 3-bit PCP Theorem. Introduction to hardness versus randomness
  19. Hardness versus randomness and Nisan-Wigderson construction. Background reading: Yao XOR lemma.
  20. More hardness versus randomness, introduction to Extractors
  21. Extractors: Trevisan's construction
  22. Expander walk extractors and their use in Nisan's prg for logspace computation. Scribe notes.

 

Handouts:

Homework 1 (due Feb 26)

Homework 2 (due March 26) 

Homework 3 (due April 18).

Homework 4 (due May 2)

 

Edited lecture notes:

  1. Lectures 1-4
  2. Lectures 5--8,
  3. Lectures 9,10(crypto)
  4. Interactive proofs
  5. PCPs
  6. Derandomization and extractors; Background: Yao XOR Lemma

SCRIBE NOTES