2000 Summer Session

Clay Mathematics Undergraduate Program

** Computational Complexity Theory **

Lecturers: David Mix Barrington and Alexis Maciel

July 16-August 5, 2000

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:
- Problems, Models, and Resources
- The Complexity of Some Problems
- Nondeterministic Computation
- Graph Reachability and Space-Bounded
- The Landscape of Complexity Classes
- Reductions and Completeness
- NP-Complete Problems
- Complete Problems for Other Complexity Classes
- Hierarchy Theorems
- AC
^{0}Circuits Cannot Compute PARITY - Proofs, Games, and Alternation (latex, ps.gz)
- Randomized Computation (latex, ps.gz)
- Interactive Proofs (latex, ps.gz)
- IP = PSPACE (latex, ps.gz)
- A Brief Look at PCP (latex, ps.gz)

- Advanced lectures:
- Three Ways to Express Problems (latex, ps.gz)
- Connecting the Three Models (latex, ps.gz)
- Algebra and Languages (latex, ps.gz)
- Non-Regular Languages and Uniformity
- Boolean Formulas, NC
^{1}, and*M*-Programs - Arithmetic and Threshold Circuits (latex, ps.gz)
- More Arithmetic and Fun With Primes (latex, ps.gz)
- Chinese Remainder Representation (latex, ps.gz)
- Towards Logspace Division (latex, ps.gz)
- Logspace Division and Its Consequences (latex, ps.gz)
- Measuring the Complexity of Proofs
- Measuring the Complexity of Proofs (Part 2)
- Polynomial-Size Frege Proofs of the Pigeonhole Principle
- Lower Bounds for Tree Resolution
- The Interpolation Method

Web page maintained by Alexis Maciel.

Last updated 3/1/01.