Surveys by Oded Goldreich
last updated: Feb 2024
The following surveys (listed in chronological order)
can be obtained in PostScript:
- O. Goldreich,
Randomness, Interaction, Proofs and Zero-Knowledge, 1987.
- O. Goldreich, Towards a Theory of Average Case Complexity, 1988.
- O. Goldreich,
Three XOR-Lemmas - An Exposition, July 1991.
- O. Goldreich, N. Nisan and A. Wigderson,
On Yao's XOR-Lemma, March 1995.
- O. Goldreich,
Probabilistic Proof Systems (surveys and notes),
1995-2008.
- O. Goldreich,
A
Computational Perspective on Sampling (survey), May 1997.
- O. Goldreich,
The Foundations of Cryptography -- An Essay,
June 1997.
- O. Goldreich,
Combinatorial Property Testing -- A Survey, 1997.
- O. Goldreich,
Review of the AS+ALMSS papers (NP=PCP[log,O(1)]), 1999.
- O. Goldreich,
Pseudorandomness, 1999.
(extended,
2000.)
- O. Goldreich,
Preface
to JofC's special issue on General Secure Multi-Party Computation, 1999.
- O. Goldreich,
Computational Complexity - a brief survey, 2000.
- O. Goldreich, M. Sudan, L. Trevisan and S. Vadhan,
Lecture Notes on Probabilistic Proofs
and Pseudorandomness, 2000.
- O. Goldreich,
A Taste of Randomized Computations,
1998, adapted 2001.
- O. Goldreich,
Cryptography and Cryptographic Protocols,
2001.
- O. Goldreich,
Zero-Knowledge twenty years after their invention,
2002.
- O. Goldreich,
Preface
to JofC's special issue on Encryption in the Bounded Storage Model, 2003.
- O. Goldreich,
Foundations of Cryptography (a primer),
July 2004.
- O. Goldreich,
Short Locally Testable Codes and Proofs (survey),
July 2004.
- O. Goldreich and A. Wigderson,
Computational Complexity, 2004.
- O. Goldreich, On Promise Problems
(a survey in memory of Shimon Even), January 2005.
- O. Goldreich, Bravely, Moderately:
A Common Theme in Four Recent Results, August 2005.
- O. Goldreich, Randomness and Computation, Dec. 2005.
- O. Goldreich and M. Sudan,
Preface
to SICOMP's special issue on Randomness and Complexity, March 2006.
- O. Goldreich and S. Vadhan,
Preface
to CC's special issue on Worst-Case vs Average-Case complexity, June 2007.
- O. Goldreich,
Probabilistic Proof Systems - A Primer,
Jun. 2008.
- O. Goldreich,
Pseudorandom Generators - A Primer, July 2008.
- O. Goldreich,
A Brief Introduction to Property Testing,
March 2010.
- O. Goldreich,
Introduction to Testing Graph Properties, March 2010.
- O. Goldreich,
General Cryptographic Protocols: The Very Basics,
March 2010.
- O. Goldreich and S. Vadhan,
On the complexity of computational problems regarding
distributions, 2010.
- O. Goldreich,
Invitation
to Complexity Theory, 2011.
- O. Goldreich,
On the
Use of Complexity in Cryptography, 2011.
- O. Goldreich, On doubly-efficient
interactive proof systems, July 2017. Includes/superseeds
- O. Goldreich, Open Problems in Property Testing of Graphs, June 2021.
- O. Goldreich,
On the Locally Testable Codes of Dinur et al
(with Constant Rate, Distance, and Locality), 2021.
- O. Goldreich, A conceptual introduction to Mathematics
(following the book of A.H. Fraenkel [1942]), Dec 2023.
- O. Goldreich, On locally-characterized expander graphs (a survey), Jan 2024.
- O. Goldreich,
On the relaxed LDC of BGHSV: A survey that corrects the record, Apr 2024.
See also books and lecture notes
by Oded Goldreich.
Back to Oded Goldreich's homepage
or to General list of Oded Goldreich's papers