DOI10.1007/978-3-642-22670-0_23zbMath1304.68074OpenAlexW2294870549MaRDI QIDQ3088189
Noam Nisan, Avi Wigderson, Oded Goldreich
Publication date: 19 August 2011
Published in: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22670-0_23
The Range of Topological Effects on Communication,
A strong direct product theorem for quantum query complexity,
Improved hardness amplification in NP,
Derandomized parallel repetition theorems for free games,
Nonuniform Indistinguishability and Unpredictability Hardcore Lemmas: New Proofs and Applications to Pseudoentropy,
Worst-Case to Average-Case Reductions for Subclasses of P,
Hardness amplification within NP against deterministic algorithms,
Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error,
Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle?,
Candidate trapdoor claw-free functions from group actions with applications to quantum protocols,
A tight computational indistinguishability bound for product distributions,
Query complexity in errorless hardness amplification,
A note on the relation between XOR and selective XOR lemmas,
Distributed Merkle's puzzles,
Unnamed Item,
Magic Adversaries Versus Individual Reduction: Science Wins Either Way,
The value of help bits in randomized and average-case complexity,
Parallel and Concurrent Security of the HB and HB + Protocols,
Basing Weak Public-Key Cryptography on Strong One-Way Functions,
Degradation and Amplification of Computational Hardness,
Hardness amplification within NP,
Parallel and concurrent security of the HB and \(HB^{+}\) protocols,
Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification,
Upper and Lower Bounds on the Power of Advice,
Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification,
Query Complexity in Errorless Hardness Amplification,
Three XOR-Lemmas — An Exposition,
Weak Oblivious Transfer from Strong One-Way Functions,
Advice Lower Bounds for the Dense Model Theorem,
Chernoff-type direct product theorems,
A Hardcore Lemma for Computational Indistinguishability: Security Amplification for Arbitrarily Weak PRGs with Optimal Stretch,
Randomness vs time: Derandomization under a uniform assumption,
Direct Sum Testing,
Average-case rigidity lower bounds
