Stop the war!
Остановите войну!
for scientists:
default search action
Studies in Complexity and Cryptography 2011
- Oded Goldreich:
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Lecture Notes in Computer Science 6650, Springer 2011, ISBN 978-3-642-22669-4
Research Contributions
- Oded Goldreich:
Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard. 1-5 - Mihir Bellare, Oded Goldreich:
Proving Computational Ability. 6-12 - Oded Goldreich, Leonid A. Levin, Noam Nisan:
On Constructing 1-1 One-Way Functions. 13-25 - Oded Goldreich, Avi Wigderson:
On the Circuit Complexity of Perfect Hashing. 26-29 - Oded Goldreich, Shafi Goldwasser, Shai Halevi:
Collision-Free Hashing from Lattice Problems. 30-39 - Oded Goldreich, David Zuckerman:
Another Proof That BPP Í PH\mathcal{BPP}\subseteq \mathcal{PH} (and More). 40-53 - Oded Goldreich:
Strong Proofs of Knowledge. 54-58 - Oded Goldreich, Salil P. Vadhan, Avi Wigderson:
Simplified Derandomization of BPP Using a Hitting Set Generator. 59-67 - Oded Goldreich, Dana Ron:
On Testing Expansion in Bounded-Degree Graphs. 68-75 - Oded Goldreich:
Candidate One-Way Functions Based on Expander Graphs. 76-87 - Oded Goldreich:
Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs. 88-97 - Oded Goldreich:
The GGM Construction Does NOT Yield Correlation Intractable Function Ensembles. 98-108 - Oded Goldreich, Madhu Sudan, Luca Trevisan:
From Logarithmic Advice to Single-Bit Advice. 109-113 - Mihir Bellare, Oded Goldreich:
On Probabilistic versus Deterministic Provers in the Definition of Proofs of Knowledge. 114-123 - Oded Goldreich:
On the Average-Case Complexity of Property Testing. 124-135 - Oded Goldreich:
A Candidate Counterexample to the Easy Cylinders Conjecture. 136-140 - Zvika Brakerski, Oded Goldreich:
From Absolute Distinguishability to Positive Distinguishability. 141-155 - Lidor Avigad, Oded Goldreich:
Testing Graph Blow-Up. 156-172 - Oded Goldreich, Tali Kaufman:
Proximity Oblivious Testing and the Role of Invariances. 173-190 - Oded Goldreich:
In a World of P=BPP. 191-232
Surveys
- Oded Goldreich:
Notes on Levin's Theory of Average-Case Complexity. 233-247 - Oded Goldreich:
Three XOR-Lemmas - An Exposition. 248-272 - Oded Goldreich, Noam Nisan, Avi Wigderson:
On Yao's XOR-Lemma. 273-301 - Oded Goldreich:
A Sample of Samplers: A Computational Perspective on Sampling. 302-332 - Oded Goldreich:
Short Locally Testable Codes and Proofs. 333-372 - Oded Goldreich:
Bravely, Moderately: A Common Theme in Four Recent Works. 373-389 - Oded Goldreich, Salil P. Vadhan:
On the Complexity of Computational Problems Regarding Distributions. 390-405 - Oded Goldreich:
Basing Non-Interactive Zero-Knowledge on (Enhanced) Trapdoor Permutations: The State of the Art. 406-421 - Oded Goldreich:
Average Case Complexity, Revisited. 422-450 - Oded Goldreich:
Basic Facts about Expander Graphs. 451-464 - Oded Goldreich:
A Brief Introduction to Property Testing. 465-469 - Oded Goldreich:
Introduction to Testing Graph Properties. 470-506 - Oded Goldreich:
Randomness and Computation. 507-539
Programmatic and Reflective Articles
- Oded Goldreich:
On Security Preserving Reductions - Revised Terminology. 540-546 - Oded Goldreich:
Contemplations on Testing Graph Properties. 547-554 - Oded Goldreich:
Another Motivation for Reducing the Randomness Complexity of Algorithms. 555-560
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.