Computing with Very Weak Random Sources

DOI10.1137/S009753979630091XzbMath0932.60008OpenAlexW2159131895MaRDI QIDQ4268718

David Zuckerman, Aravind Srinivasan

Publication date: 28 October 1999

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s009753979630091x

zbMATH Keywords

derandomizationpseudorandom generatorsrandomized computationmeasures of informationhardness of approximationpseudorandomnessexpander graphstime-space tradeoffshashing lemmasimperfect sources of randomness

Mathematics Subject Classification ID

Combinatorial probability (60C05) Measures of information, entropy (94A17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Unnamed Item ⋮ Optimal Coin Flipping ⋮ Simpler session-key generation from short random passwords ⋮ Lower bounds for non-black-box zero knowledge ⋮ Pseudorandom generators without the XOR lemma ⋮ Extractors from Reed-Muller codes ⋮ Extracting Kolmogorov complexity with applications to dimension zero-one laws ⋮ A Linear Lower Bound on the Communication Complexity of Single-Server Private Information Retrieval ⋮ Non-interactive timestamping in the bounded-storage model ⋮ Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly ⋮ Better short-seed quantum-proof extractors ⋮ Finding Collisions in Interactive Protocols---Tight Lower Bounds on the Round and Communication Complexities of Statistically Hiding Commitments ⋮ Extracting randomness: A survey and new constructions