Extractors for weak random sources and their applications

DOI10.1007/BFb0054363zbMath1502.68366MaRDI QIDQ5054851

David Zuckerman

Publication date: 9 December 2022

Published in: Algorithm Theory — SWAT'98 (Search for Journal in Brave)

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generating quasi-random sequences from semi-random sources
• Expanders, randomness, or time versus space
• Randomness is linear in space
• Simulating BPP using a general weak random source
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Explicit OR-dispersers with polylogarithmic degree
• Weak Random Sources, Hitting Sets, and BPP Simulations
• Expanders that beat the eigenvalue bound