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

DOI10.1016/S0304-3975(99)00024-9zbMath0930.68064OpenAlexW2083027849MaRDI QIDQ1960516

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

Publication date: 12 January 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(99)00024-9

zbMATH Keywords

EXP function

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (4)

Compression of partially defined information ⋮ On pseudorandomness and resource-bounded measure ⋮ Extracting all the randomness and reducing the error in Trevisan's extractors ⋮ Randomness vs time: Derandomization under a uniform assumption

Cites Work

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

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