Studies in Complexity and Cryptography

A collection of some unpublished works by Oded Goldreich

This collection was compiled in 2010 (and appeared as LNCS 6650, 2011 [See volume's cover]). 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.

PART I: RESEARCH CONTRIBUTIONS

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

PART II: SURVEYS

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

PART III: PROGRAMATIC / REFLECTIVE

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

Brief biographies of the authors.

[cover of volume LNCS 6650.]
click 4 big

Studies in Complexity and Cryptography

Miscellanea on the Interplay between Randomness and Computation

©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.