Limitations of Hardness vs. Randomness under Uniform Reductions

DOI10.1007/978-3-540-85363-3_37zbMath1159.68009OpenAlexW1850905020MaRDI QIDQ3541813

Dan Gutfreund, Salil P. Vadhan

Publication date: 27 November 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85363-3_37

zbMATH Keywords

derandomizationpseudorandom generatorsblack-box reductions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items (8)

Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? ⋮ The Complexity of Complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets ⋮ Limits on the Computational Power of Random Strings ⋮ Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification ⋮ Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification

This page was built for publication: Limitations of Hardness vs. Randomness under Uniform Reductions