Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 1 Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard
3. Altmetric Badge
   Chapter 2 Proving Computational Ability
4. Altmetric Badge
   Chapter 3 On Constructing 1-1 One-Way Functions
5. Altmetric Badge
   Chapter 4 On the Circuit Complexity of Perfect Hashing
6. Altmetric Badge
   Chapter 5 Collision-Free Hashing from Lattice Problems
7. Altmetric Badge
   Chapter 6 Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)
8. Altmetric Badge
   Chapter 7 Strong Proofs of Knowledge
9. Altmetric Badge
   Chapter 8 Simplified Derandomization of BPP Using a Hitting Set Generator
10. Altmetric Badge
    Chapter 9 On Testing Expansion in Bounded-Degree Graphs
11. Altmetric Badge
    Chapter 10 Candidate One-Way Functions Based on Expander Graphs
12. Altmetric Badge
    Chapter 11 Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs
13. Altmetric Badge
    Chapter 12 The GGM Construction Does NOT Yield Correlation Intractable Function Ensembles
14. Altmetric Badge
    Chapter 13 From Logarithmic Advice to Single-Bit Advice
15. Altmetric Badge
    Chapter 14 On Probabilistic versus Deterministic Provers in the Definition of Proofs of Knowledge
16. Altmetric Badge
    Chapter 15 On the Average-Case Complexity of Property Testing
17. Altmetric Badge
    Chapter 16 A Candidate Counterexample to the Easy Cylinders Conjecture
18. Altmetric Badge
    Chapter 17 From Absolute Distinguishability to Positive Distinguishability
19. Altmetric Badge
    Chapter 18 Testing Graph Blow-Up
20. Altmetric Badge
    Chapter 19 Proximity Oblivious Testing and the Role of Invariances
21. Altmetric Badge
    Chapter 20 In a World of P=BPP
22. Altmetric Badge
    Chapter 21 Notes on Levin’s Theory of Average-Case Complexity
23. Altmetric Badge
    Chapter 22 Three XOR-Lemmas — An Exposition
24. Altmetric Badge
    Chapter 23 On Yao’s XOR-Lemma
25. Altmetric Badge
    Chapter 24 A Sample of Samplers: A Computational Perspective on Sampling
26. Altmetric Badge
    Chapter 25 Short Locally Testable Codes and Proofs
27. Altmetric Badge
    Chapter 26 Bravely, Moderately: A Common Theme in Four Recent Works
28. Altmetric Badge
    Chapter 27 On the Complexity of Computational Problems Regarding Distributions
29. Altmetric Badge
    Chapter 28 Basing Non-Interactive Zero-Knowledge on (Enhanced) Trapdoor Permutations: The State of the Art
30. Altmetric Badge
    Chapter 29 Average Case Complexity, Revisited
31. Altmetric Badge
    Chapter 30 Basic Facts about Expander Graphs
32. Altmetric Badge
    Chapter 31 A Brief Introduction to Property Testing
33. Altmetric Badge
    Chapter 32 Introduction to Testing Graph Properties
34. Altmetric Badge
    Chapter 33 Randomness and Computation
35. Altmetric Badge
    Chapter 34 On Security Preserving Reductions – Revised Terminology
36. Altmetric Badge
    Chapter 35 Contemplations on Testing Graph Properties
37. Altmetric Badge
    Chapter 36 Another Motivation for Reducing the Randomness Complexity of Algorithms