Complexity Theory - Expositions

Oded Goldreich

This page provides access to an eclectic collection of expositions. I have arranged them in two main sets. The first set consists of texts that were written with the aim of fitting a complexity theory course and/or seminar (and are actually extracts from a draft of a book). In contrast, the second set consists of texts written for general purposes, and typically envision a general TOC reader.

First Set: for a complexity theory course

The following numbered texts are extracts from a draft of a book (entitled Computational Complexity: A Conceptual Perspective). This book is written with the aim of fitting a complexity theoretic course and/or seminar. In fact, the extracts have been used in the course that I have been teaching (where A indicates auxiliary material, and T indicates material actually taught).
  1. T/A: A brief overview to Complexity Theory (a teaser), Nov. 2005.
  2. A: A proof of Toda's Theorem, Nov. 2005.
  3. A: Proofs of the emulation of IP by AM and the round-complexity speed-up, Nov. 2005.
  4. A: A proof of the #P-completeness of the permanent, Nov. 2005.
  5. T/A: Four Advanced Topics Related to NP and NPC, Nov. 2005.
  6. A: Proving Yao's XOR Lemma via the Direct Product Lemma, Nov. 2005.
  7. T: On P/poly and PH, Nov. 2005.
  8. T: More resources, more power?, Dec. 2005.
  9. A: The preliminaries - computational tasks and model, Dec. 2005.
  10. A: Proving that Undirected Connectivity is in L (with a long appendix on expanders), Dec. 2005.
  11. T: Space Complexity, Dec. 2005.
  12. A: On Error Correcting Codes, Jan. 2006.
  13. T: Randomized Complexity Classes, Jan. 2006.
  14. T: P, NP and NP-Completeness, Jan. 2006.
  15. T: Counting Problems, Jan. 2006.
  16. T: Probabilistic Proof Systems, Jan. 2006.
  17. T: Pseudorandom Generators, Jan. 2006.
  18. T: Average-Case Complexity, Jan. 2006.
  19. T: Approximation Problems, Jan. 2006.
  20. A: Probabilistic Preliminaries and Advanced Topics in Randomization, Jan. 2006.
  21. T/A: Amplification of Hardness, Feb. 2006.
See also additional (related) material and lecture notes and surveys.

Second Set: for wider use

The following unnumbered texts were written for general purposes, and typically envision a general TOC reader (rather than a student of a complexity theory course).


Related Material (available on-line)

Back to Oded Goldreich's homepage.