Some Complexity Related Papers by Oded Goldreich

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.