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).
 T/A:
A
brief overview to Complexity Theory (a teaser), Nov. 2005.
 A:
A
proof of Toda's Theorem, Nov. 2005.
 A:
Proofs
of the emulation of IP by AM and the roundcomplexity speedup, Nov. 2005.
 A:
A
proof of the #Pcompleteness of the permanent, Nov. 2005.
 T/A:
Four
Advanced Topics Related to NP and NPC, Nov. 2005.
 A:
Proving
Yao's XOR Lemma via the Direct Product Lemma, Nov. 2005.
 T:
On
P/poly and PH, Nov. 2005.
 T:
More
resources, more power?, Dec. 2005.
 A:
The
preliminaries  computational tasks and model, Dec. 2005.
 A:
Proving
that Undirected Connectivity is in L (with a long appendix
on expanders), Dec. 2005.
 T:
Space
Complexity, Dec. 2005.
 A:
On
Error Correcting Codes, Jan. 2006.
 T:
Randomized
Complexity Classes, Jan. 2006.
 T:
P, NP
and NPCompleteness, Jan. 2006.
 T:
Counting
Problems, Jan. 2006.
 T:
Probabilistic
Proof Systems, Jan. 2006.
 T:
Pseudorandom
Generators, Jan. 2006.
 T:
AverageCase
Complexity, Jan. 2006.
 T:
Approximation
Problems, Jan. 2006.
 A:
Probabilistic
Preliminaries and Advanced Topics in Randomization, Jan. 2006.
 T/A:
Amplification
of Hardness, Feb. 2006.
See also additional (related) material
and lecture notes
and surveys.
See also less related material
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).

Randomness, Interaction, Proofs and ZeroKnowledge, 1987.
See a revised version of the part on
Computational Randomness, 1987 (rev. 1997).
 Towards a Theory of Average Case Complexity, 1988.
See revised
Notes
on Levin's Theory of AverageCase Complexity, 1997.

Three XORLemmas  An Exposition, July 1991.
 Pseudorandomness (surveys), 19872008.
 Probabilistic Proof Systems (surveys and notes),
19952008.
 A
Computational Perspective on Sampling (survey), May 1997.

Combinatorial Property Testing  A Survey, 1997.

Review of the AS+ALMSS papers (NP=PCP[log,O(1)]), 1999.
 A Taste of Randomized Computations,
1998, adapted 2001.
 ZeroKnowledge twenty years
after their invention, 2002.
 Foundations of Cryptography (a primer),
July 2004.
 Short Locally Testable Codes and Proofs (survey),
July 2004.
 On Promise Problems
(a survey in memory of Shimon Even), January 2005.
 On Teaching the Basics of Complexity Theory,
February 2005.
(Contains a version of the
brief
overview to Complexity Theory, revised Nov. 2005.)
 A common theme in recent results
regarding Approximate Counting Perfect Matchings,
ZigZag Expanders, Undirected Connectivity in LogSpace,
and the construction of PCP systems, Sept. 2005.
 Randomness and Computation
(intended for nonTOC readers), Dec. 2005.
 Probabilistic Proof Systems  A Primer,
June 2008.
 Pseudorandom Generators  A Primer, July
2008.
 A Brief Introduction to Property Testing,
March 2010.
 Introduction to Testing Graph Properties,
March 2010.
OTHER MATERIAL AVAILABLE ONLINE
Related Material (available online)
Back to Oded Goldreich's homepage.