Complexity Theory - Expositions
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).
See also additional (related) material
and lecture notes
brief overview to Complexity Theory (a teaser), Nov. 2005.
proof of Toda's Theorem, Nov. 2005.
of the emulation of IP by AM and the round-complexity speed-up, Nov. 2005.
proof of the #P-completeness of the permanent, Nov. 2005.
Advanced Topics Related to NP and NPC, Nov. 2005.
Yao's XOR Lemma via the Direct Product Lemma, Nov. 2005.
P/poly and PH, Nov. 2005.
resources, more power?, Dec. 2005.
preliminaries - computational tasks and model, Dec. 2005.
that Undirected Connectivity is in L (with a long appendix
on expanders), Dec. 2005.
Complexity, Dec. 2005.
Error Correcting Codes, Jan. 2006.
Complexity Classes, Jan. 2006.
and NP-Completeness, Jan. 2006.
Problems, Jan. 2006.
Proof Systems, Jan. 2006.
Generators, Jan. 2006.
Complexity, Jan. 2006.
Problems, Jan. 2006.
Preliminaries and Advanced Topics in Randomization, Jan. 2006.
of Hardness, Feb. 2006.
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 Zero-Knowledge, 1987.
See a revised version of the part on
Computational Randomness, 1987 (rev. 1997).
- Towards a Theory of Average Case Complexity, 1988.
on Levin's Theory of Average-Case Complexity, 1997.
Three XOR-Lemmas - An Exposition, July 1991.
- Pseudorandomness (surveys), 1987-2008.
- Probabilistic Proof Systems (surveys and notes),
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.
- Zero-Knowledge twenty years
after their invention, 2002.
- Foundations of Cryptography (a primer),
- Short Locally Testable Codes and Proofs (survey),
- On Promise Problems
(a survey in memory of Shimon Even), January 2005.
- On Teaching the Basics of Complexity Theory,
(Contains a version of the
overview to Complexity Theory, revised Nov. 2005.)
- A common theme in recent results
regarding Approximate Counting Perfect Matchings,
Zig-Zag Expanders, Undirected Connectivity in Log-Space,
and the construction of PCP systems, Sept. 2005.
- Randomness and Computation
(intended for non-TOC readers), Dec. 2005.
- Probabilistic Proof Systems - A Primer,
- Pseudorandom Generators - A Primer, July
- A Brief Introduction to Property Testing,
- Introduction to Testing Graph Properties,
OTHER MATERIAL AVAILABLE ON-LINE
Related Material (available on-line)
Back to Oded Goldreich's homepage.