This collection was compiled in 2010 (and appeared as LNCS 6650, 2011). It consists of revised versions of articles that were not officilally published before, for a variety of reasons. The collection is composed of three types of articles.

- Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle is NP-Hard
- M. Bellare and O. Goldreich, Proofs of Computational Ability
- O. Goldreich, L.A. Levin, and N. Nisan, On Constructing 1-1 One-way Functions
- O. Goldreich and A. Wigderson, On the Circuit Complexity of Perfect Hashing
- O. Goldreich, S. Goldwasser, and S. Halevi, Collision-Free Hashing from Lattice Problems
- O. Goldreich and D. Zuckerman, Another proof that BPP subseteq PH (and more)
- Strong Proofs Of Knowledge
- O. Goldreich, S. Vadhan and A. Wigderson, Simplified Derandomization of BPP using a Hitting Set Generator
- O. Goldreich and D. Ron, On Testing Expansion in Bounded-Degree Graphs
- Candidate One-Way Functions Based on Expander Graphs
- Using the FGLSS-reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs
- The GGM Construction does NOT yield Correlation Intractable Function Ensembles
- O. Goldreich, M. Sudan and L. Trevisan, From logarithmic advice to single-bit advice
- M. Bellare and O. Goldreich, On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge
- On the Average-Case Complexity of Property Testing
- Z. Brakerski and O. Goldreich, From absolute distinguishability to positive distinguishability
- A Candidate Counterexample to the Easy Cylinders Conjecture
- L. Avigad and O. Goldreich, Testing Graph Blow-Up
- O. Goldreich and T. Kaufman, Proximity Oblivious Testing and the Role of Invariances
- In a World of P=BPP

- On Yao's XOR-Lemma (with N. Nisan and A. Wigderson.)
- Three XOR-Lemmas -- An Exposition
- A Sample of Samplers -- A Computational Perspective on Sampling
- Notes on Levin's Theory of Average-Case Complexity
- Short Locally Testable Codes and Proofs - A Survey in Two Parts
- Bravely, Moderately: A Common Theme in Four Recent Results
- Basing Non-Interactive Zero-Knowledge on (Enhanced) Trapdoor Permutations: The State of the art
- On the complexity of computational problems regarding distributions (with Salil Vadhan)
- Average-Case Complexity, Revisited
- Basic Facts about Expander Graphs
- A Brief Introduction to Property Testing
- Introduction to Testing Graph Properties

- On Security Preserving Reductions - Revised Terminology
- Contemplations on testing graph properties
- Another motivation for reducing the randomness complexity of algorithms

©Copyright 2010 by Oded Goldreich.

Permission to make copies of part or all of this work for personal
or classroom use is granted without fee provided that copies
are not made or distributed for profit or commercial
advantage and that new copies bear this notice and the full
citation on the first page. Abstracting with credit is permitted.

Back to Oded Goldreich's homepage.