CSE 713 - Probabilistically Checkable Proofs and
Inapproximability
Fall 2004
1. General lectures, textbooks, and survey papers
- Madhu Sudan's lecture notes on PCP at the Graduate Summer School on Computational
Complexity, organized by the Park City Mathematical Institute and held at
the Institute for Advanced Study, Princeton, NJ, July 16 - August 5, 2000.
- Arora's lecture notes on "complexity reductions" given
at IAS-Park City
- Uriel Feige's
course
- L. Lovász: Interactive proofs: a new look at passwords, proofs, and refereeing
- Sanjeev Arora and Carsten Lund, Hardness of Approximations, In Approximation Algorithms
for NP-hard Problems, Dorit Hochbaum, Ed. PWS Publishing , 1996.
- Sanjeev Arora's PhD Thesis, Probabilistic checking of proofs and the hardness of approximation
problems, UC Berkeley, 1994
- Fourier
Transform and TCS (a class by Vazirani).
- Theorist's
Toolkit (Arora's course at Princeton)
- Advanced
Complexity Theory(Arora's course at Princeton)
- Approximation
Algorithm (Yuval Rabani's course at Cornell)
-
Advanced Complexity (Dan Spielman's course at MIT)
- Computational Complexity
(Luca Trevisan's course at Berkeley)
2. Some key people in the field
Sanjeev Arora | Laszlo Babai | Mihir Bellare | Uriel Feige | Lance Fortnow | Oded Goldreich
| Johan Hastad | Joe
Kilian | Laci Lovasz
| Carsten Lund | Silvio Micali
| Ran
Raz | Muli Safra | Luca
Trevisan | Madhu Sudan
| Uri Swick | Mario Szegedy
3. Online Journals & other links