See brief surveys (2000 and 2004), a book (2008), and other material.

The following papers can be obtained in PostScript (papers in REVERSE CHRONOLOGICAL ORDER):

- A. Akavia, O. Goldreich, S. Goldwasser, and D. Moshkovitz, On Basing One-Way Functions on NP-Hardness, 2005.
- E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan and S. Vadhan, Short PCPs verifiable in polylogarithmic time, 2005
- O. Goldreich, Bravely, Moderately: A Common Theme in Four Recent Results, August 2005.
- O. Goldreich, On Promise Problems (a survey in memory of Shimon Even), January 2005.
- O. Goldreich, Short Locally Testable Codes and Proofs (survey), July 2004.
- O. Goldreich, M. Sudan and L. Trevisan, From logarithmic advice to single-bit advice, 2004.
- E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan and S. Vadhan, Robust PCPs of Proximity, Shorter PCPs and Applications to Coding, March 2004.
- O. Goldreich, S. Goldwasser and A. Nussboim, On the Implementation of Huge Random Objects, 2003.
- E. Ben-Sasson, O. Goldreich and M. Sudan, Bounds on 2-Query Codeword Testing, 2003.
- O. Goldreich and M. Sudan, Locally Testable Codes and PCPs of Almost-Linear Length, August 2002.
- O. Goldreich and A. Wigderson, Deradomization that is rarely wrong from short advice that is typically good, 2002.
- O. Goldreich, Using the FGLSS-reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs, 2001.
- B. Barak and O. Goldreich, Universal Arguments and their Applications, 2001.
- O. Goldreich, H. Karloff, L. Schulman, and L. Trevisan, Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval, 2001.
- B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. Vadhan and K. Yang, On the (Im)possibility of Obfuscating Programs, 2001.
- O. Goldreich, S. Vadhan, and A. Wigderson, On Interactive Proofs with a Laconic Prover, 2001.
- O. Goldreich and L. Trevisan, Three Theorems regarding Testing Graph Properties, 2001.
- O. Goldreich, Candidate One-Way Functions Based on Expander Graphs, 2000.
- O. Goldreich and A. Wigderson, On Pseudorandomness with respect to Deterministic Observers, May 2000.
- O. Goldreich, S. Vadhan, and A. Wigderson, Simplified derandomization of BPP using a hitting set generator, Dec. 1999.
- O. Goldreich and A. Wigderson, Improved derandomization of BPP using a hitting set generator, May 1999.
- O. Goldreich, D. Micciancio, S. Safra, and J.P. Seifert, Approximating shortest lattice vectors is not harder than approximating closest lattice vectors, 1999.
- O. Goldreich, A. Sahai and S. Vadhan, Can Statistical Zero-Knowledge be Made Non-Interactive? or On the Relationship of SZK and NISZK, 1998.
- O. Goldreich and S. Vadhan, Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of this Class, 1998.
- Z. Bar-Yossef, O. Goldreich, and A. Wigderson, Deterministic Amplification of Space Bounded Probabilistic Algorithms, 1998.
- M. Bellare, O. Goldreich and E. Petrank, Uniform Generation of NP-witnesses using an NP-oracle, 1998.
- O. Goldreich and M. Sudan, Computational Indistinguishability: A Sample Hierarchy, March 1998.
- O. Goldreich, A. Sahai and S. Vadhan, Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge, 1998.
- O. Goldreich and D. Zuckerman, Another proof that BPP subseteq PH (and more), September 1997.
- O. Goldreich and S. Goldwasser, On the Limits of Non-Approximability of Lattice Problems, Sept. 1997.
- O. Goldreich, A Computational Perspective on Sampling (survey), May 1997.
- O. Goldreich and B. Meyer, Computational Indistinguishability - Algorithms vs. Circuits, December 1996.
- O. Goldreich, and S. Safra, A Combinatorial Consistency Lemma with application to the PCP Theorem, 1996.
- O. Goldreich and A. Wigderson, On the Circuit Complexity of Perfect Hashing, July 1996.
- O. Goldreich and E. Petrank, Quantifying Knowledge Complexity, revised July 1996.
- O. Goldreich and J. Hastad, On the Complexity of Interactive Proof with Bounded Communication, Feb. 1996. (rev. April 1997)
- M. Bellare, O. Goldreich and M. Sudan, Free Bits, PCPs and Non-Approximability, 1995.
- I. Damgard, O. Goldreich and A. Wigderson,

Information Theory versus Complexity Theory: Another Test Case, September 1995. - O. Goldreich, L.A. Levin and N. Nisan , On Constructing 1-1 One-Way Functions, June 1995.
- O. Goldreich, Probabilistic Proof Systems (survey), 1995.
- O. Goldreich, N. Nisan and A. Wigderson, On Yao's XOR-Lemma, March 1995.
- O. Goldreich, R. Ostrovsky and E. Petrank,

Computational Complexity and Knowledge Complexity, revised March 1995. - O. Goldreich and A. Wigderson, Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing, November 1994.
- R. Canetti, G. Even and O. Goldreich,

Lower Bounds for Sampling Algorithms for Estimating the Average, October 1994. - M. Blum and O. Goldreich, Towards a Computational Theory of Statistical Tests, 1992.
- G. Even, O. Goldreich, M. Luby, N. Nisan and B. Velickovic,

Approximations of General Independent Distributions, 1992. - R. Chang, B. Chor, O. Goldreich, J. Hartmanis, J. Hastad,
D. Ranjan and P. Rohatgi,

The Random Oracle Hypothesis is False, July 1992. - N. Alon, O. Goldreich J. Hastad and R. Peralta, Simple Constructions of Almost $k$-wise Independent Random Variables, June 1992. (See also an Addendum.)
- M. Bellare, O. Goldreich and S. Goldwasser, Randomness in Interactive Proofs, August 1991. Addendum, May 1997.
- O. Goldreich, Three XOR-Lemmas - An Exposition, July 1991.
- O. Goldreich, R. Impagliazzo, L.A. Levin,
R. Venkatesan and D. Zuckerman,

Security Preserving Amplification of Hardness, August 1990. - R. Canetti and O. Goldreich,

Bounds on Tradeoffs between Randomness and Communication Complexity, August 1990. - O. Goldreich and L.A. Levin,
*Hard-core Predicates for any One-way Function*, 1989.

See Three XOR-Lemmas - An Exposition. - O. Goldreich, A Note on Computational Indistinguishability, 1989.
- S. Ben-David, B. Chor, O. Goldreich and M. Luby, On the Theory of Average Case Complexity, 1989.
- M. Furer, O. Goldreich, Y. Mansour, M. Sipser, and S. Zachos, On Completeness and Soundness in Interactive Proof Systems, 1989.
- O. Goldreich,
Randomness, Interaction, Proofs and Zero-Knowledge (a survey), 1987.
(Appeared in
*The Universal Turing Machine: A Half-Century Survey*, R. Herken (ed.), Oxford University Press, 1988.) - O. Goldreich and S. Micali, Increasing the Expansion of Pseudorandom Generators, 1984.

Low quality PostScript files of very old papers

- B. Chor, J. Freidmann, O. Goldreich, J. Hastad,
S. Rudich and R. Smolensky,

The Bit Extraction Problem or t-Resilient Functions, 1985. - B. Chor and O. Goldreich, On the power of two-points based sampling, 1985.

Back to Oded Goldreich's homepage or to General list of Oded Goldreich's papers