Basic Lectures 1 to 10 and Advanced Lectures 4 and 5 are in PDF. The others are in Latex and compressed (gzip) Postscript. If you decide to Latex the notes yourself, you will need the file PCMInotes.tex.

• Basic lectures:
  1. Problems, Models, and Resources
  2. The Complexity of Some Problems
  3. Nondeterministic Computation
  4. Graph Reachability and Space-Bounded
  5. The Landscape of Complexity Classes
  6. Reductions and Completeness
  7. NP-Complete Problems
  8. Complete Problems for Other Complexity Classes
  9. Hierarchy Theorems
  10. AC⁰ Circuits Cannot Compute PARITY
  11. Proofs, Games, and Alternation (latex, ps.gz)
  12. Randomized Computation (latex, ps.gz)
  13. Interactive Proofs (latex, ps.gz)
  14. IP = PSPACE (latex, ps.gz)
  15. A Brief Look at PCP (latex, ps.gz)

• Advanced lectures:
  1. Three Ways to Express Problems (latex, ps.gz)
  2. Connecting the Three Models (latex, ps.gz)
  3. Algebra and Languages (latex, ps.gz)
  4. Non-Regular Languages and Uniformity
  5. Boolean Formulas, NC¹, and M-Programs
  6. Arithmetic and Threshold Circuits (latex, ps.gz)
  7. More Arithmetic and Fun With Primes (latex, ps.gz)
  8. Chinese Remainder Representation (latex, ps.gz)
  9. Towards Logspace Division (latex, ps.gz)
  10. Logspace Division and Its Consequences (latex, ps.gz)
  11. Measuring the Complexity of Proofs
  12. Measuring the Complexity of Proofs (Part 2)
  13. Polynomial-Size Frege Proofs of the Pigeonhole Principle
  14. Lower Bounds for Tree Resolution
  15. The Interpolation Method