Skip to main content
SpringerLink
Log in
Book cover

Studies in Complexity and Cryptography

Miscellanea on the Interplay between Randomness and Computation

  • Book
  • © 2011

Overview

Editors:
  1. Oded Goldreich

    1. Faculty of Mathematics and Computer Science, Weizmann Institute of Science, Rehovot, Israel

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • High quality selected papers
  • Unique visibility
  • State of the art research

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 6650)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 79.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 99.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (36 chapters)

  1. Front Matter

    Download chapter PDF

  2. Research Contributions

    1. Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard

      • Oded Goldreich
      Pages 1-5

    2. Proving Computational Ability

      • Mihir Bellare, Oded Goldreich
      Pages 6-12

    3. On Constructing 1-1 One-Way Functions

      • Oded Goldreich, Leonid A. Levin, Noam Nisan
      Pages 13-25

    4. On the Circuit Complexity of Perfect Hashing

      • Oded Goldreich, Avi Wigderson
      Pages 26-29

    5. Collision-Free Hashing from Lattice Problems

      • Oded Goldreich, Shafi Goldwasser, Shai Halevi
      Pages 30-39

    6. Another Proof That \(\mathcal{BPP}\subseteq \mathcal{PH}\) (and More)

      • Oded Goldreich, David Zuckerman
      Pages 40-53

    7. Strong Proofs of Knowledge

      • Oded Goldreich
      Pages 54-58

    8. Simplified Derandomization of BPP Using a Hitting Set Generator

      • Oded Goldreich, Salil Vadhan, Avi Wigderson
      Pages 59-67

    9. On Testing Expansion in Bounded-Degree Graphs

      • Oded Goldreich, Dana Ron
      Pages 68-75

    10. Candidate One-Way Functions Based on Expander Graphs

      • Oded Goldreich
      Pages 76-87

    11. Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs

      • Oded Goldreich
      Pages 88-97

    12. The GGM Construction Does NOT Yield Correlation Intractable Function Ensembles

      • Oded Goldreich
      Pages 98-108

    13. From Logarithmic Advice to Single-Bit Advice

      • Oded Goldreich, Madhu Sudan, Luca Trevisan
      Pages 109-113

    14. On Probabilistic versus Deterministic Provers in the Definition of Proofs of Knowledge

      • Mihir Bellare, Oded Goldreich
      Pages 114-123

    15. On the Average-Case Complexity of Property Testing

      • Oded Goldreich
      Pages 124-135

    16. A Candidate Counterexample to the Easy Cylinders Conjecture

      • Oded Goldreich
      Pages 136-140

    17. From Absolute Distinguishability to Positive Distinguishability

      • Zvika Brakerski, Oded Goldreich
      Pages 141-155

    18. Testing Graph Blow-Up

      • Lidor Avigad, Oded Goldreich
      Pages 156-172

    19. Proximity Oblivious Testing and the Role of Invariances

      • Oded Goldreich, Tali Kaufman
      Pages 173-190
Back to top

Keywords

About this book

This book presents a collection of 36 pieces of scientific work in the areas of complexity theory and foundations of cryptography: 20 research contributions, 13 survey articles, and 3 programmatic and reflective viewpoint statements. These so far formally unpublished pieces were written by Oded Goldreich, some in collaboration with other scientists.
The articles included in this book essentially reflect the topical scope of the scientific career of Oded Goldreich now spanning three decades. In particular the topics dealt with include average-case complexity, complexity of approximation, derandomization, expander graphs, hashing functions, locally testable codes, machines that take advice, NP-completeness, one-way functions, probabilistically checkable proofs, proofs of knowledge, property testing, pseudorandomness, randomness extractors, sampling, trapdoor permutations, zero-knowledge, and non-iterative zero-knowledge.
All in all, this potpourri of studies in complexity and cryptography constitutes a most valuable contribution to the field of theoretical computer science centered around the personal achievements and views of one of its outstanding representatives.

Editors and Affiliations

  • Faculty of Mathematics and Computer Science, Weizmann Institute of Science, Rehovot, Israel

    Oded Goldreich

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation