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

Front Matter....Pages -
Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard....Pages 1-5
Proving Computational Ability....Pages 6-12
On Constructing 1-1 One-Way Functions....Pages 13-25
On the Circuit Complexity of Perfect Hashing....Pages 26-29
Collision-Free Hashing from Lattice Problems....Pages 30-39
Another Proof That $\\mathcal{BPP}\\subseteq \\mathcal{PH}$ (and More)....Pages 40-53
Strong Proofs of Knowledge....Pages 54-58
Simplified Derandomization of BPP Using a Hitting Set Generator....Pages 59-67
On Testing Expansion in Bounded-Degree Graphs....Pages 68-75
Candidate One-Way Functions Based on Expander Graphs....Pages 76-87
Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs....Pages 88-97
The GGM Construction Does NOT Yield Correlation Intractable Function Ensembles....Pages 98-108
From Logarithmic Advice to Single-Bit Advice....Pages 109-113
On Probabilistic versus Deterministic Provers in the Definition of Proofs of Knowledge....Pages 114-123
On the Average-Case Complexity of Property Testing....Pages 124-135
A Candidate Counterexample to the Easy Cylinders Conjecture....Pages 136-140
From Absolute Distinguishability to Positive Distinguishability....Pages 141-155
Testing Graph Blow-Up....Pages 156-172
Proximity Oblivious Testing and the Role of Invariances....Pages 173-190
In a World of P=BPP....Pages 191-232
Notes on Levin’s Theory of Average-Case Complexity....Pages 233-247
Three XOR-Lemmas — An Exposition....Pages 248-272
On Yao’s XOR-Lemma....Pages 273-301
A Sample of Samplers: A Computational Perspective on Sampling....Pages 302-332
Short Locally Testable Codes and Proofs....Pages 333-372
Bravely, Moderately: A Common Theme in Four Recent Works....Pages 373-389
On the Complexity of Computational Problems Regarding Distributions....Pages 390-405
Basing Non-Interactive Zero-Knowledge on (Enhanced) Trapdoor Permutations: The State of the Art....Pages 406-421
Average Case Complexity, Revisited....Pages 422-450
Basic Facts about Expander Graphs....Pages 451-464
A Brief Introduction to Property Testing....Pages 465-469
Introduction to Testing Graph Properties....Pages 470-506
Randomness and Computation....Pages 507-539
On Security Preserving Reductions – Revised Terminology....Pages 540-546
Contemplations on Testing Graph Properties....Pages 547-554
Another Motivation for Reducing the Randomness Complexity of Algorithms....Pages 555-560
Back Matter....Pages -