Below you will find Latex and compressed (gzip) Postscript versions of the lecture notes. If you decide to Latex the notes yourself, you will need the file PCMInotes.tex.

• Basic lectures:
  1. Problems, Models, and Resources (latex, ps.gz)
  2. The Complexity of Some Problems (latex, ps.gz)
  3. Nondeterministic Computation (latex, ps.gz)
  4. Graph Reachability and Space-Bounded Computation (latex, ps.gz)
  5. The Landscape of Complexity Classes (latex, ps.gz)
  6. Reductions and Completeness (latex, ps.gz)
  7. Circuit Satisfiability (latex, ps.gz)
  8. Complete Problems for Other Complexity Classes (latex, ps.gz)
  9. Hierarchy Theorems (latex, ps.gz)
  10. AC⁰ Circuits Cannot Compute PARITY (latex, ps.gz)
  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 (latex, ps.gz)
  5. Boolean Formulas, NC¹, and M-Programs (latex, ps.gz)
  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 (latex, ps.gz)
  12. Measuring the Complexity of Proofs (Part 2) (latex, ps.gz)
  13. Polynomial-Size Frege Proofs of the Pigeonhole Principle (latex, ps.gz)
  14. Lower Bounds for Tree Resolution (latex, ps.gz)
  15. The Interpolation Method (latex, ps.gz)