Worst-case hardness suffices for derandomization: A new method for hardness-randomness trade-offs

DOI10.1007/3-540-63165-8_175zbMath1401.68093OpenAlexW1858119873MaRDI QIDQ4571950

Alexander E. Andreev, José D. P. Rolim, Andrea E. F. Clementi

Publication date: 4 July 2018

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-63165-8_175

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

THEORETICALLY EFFECTIVE ASYMPTOTICALLY OPTIMAL UNIVERSAL CODING OF PARTIALLY DEFINED SOURCES ⋮ Pseudorandom generators without the XOR lemma

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ramanujan graphs
• Eigenvalues and expanders
• Hardness vs randomness
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Weak Random Sources, Hitting Sets, and BPP Simulations

This page was built for publication: Worst-case hardness suffices for derandomization: A new method for hardness-randomness trade-offs