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

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.

• On the analysis of the Zig-Zag product, Jan. 2023.
  Superseded by a more intuitive analysis that provides a better result, June 2024.
• Arithmetization in probabilistic proof systems, July 2023.
• On parallel repetitions of interactive proof systems, Sept 2023.
• On constructing PRGs based on any OWF, Oct 2023.

See also less related material

• Valiant's Polynomial-Size Monotone Formula for Majority, May 2011.
• On the KW games, Dec. 2021.
• On the algorithmic method for circuit lower bounds, Jan. 2023.
• On the approximation method for circuit lower bounds, Mar. 2023.
• Computing approximate majority in AC0, Mar. 2023.
• HDX: from local expansion to global expansion , July 2024.

Second Set: for wider use

• 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.
  See revised Notes 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), 1995-2008.
• 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.
• Zero-Knowledge 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, 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, 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 ON-LINE

• Two sets of lecture notes: detailed notes written by students (1999) and less detailed notes written by O.G. (2002).
• Two surveys: one focusing on the high-level appproach and the other including coverage of lower bounds (co-auothered by Avi Wigderson).

Related Material (available on-line)

• Background: draft of a textbook in Hebrew on Computability and Basic Complexity Theory.
• Modern Cryptography, Probabilistic Proofs and Pseudorandomness (1998).
• Two lectures on advance topics in computability, 2002.

Back to Oded Goldreich's homepage.