Computing with Very Weak Random Sources
From MaRDI portal
Publication:4268718
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
derandomizationpseudorandom generatorsrandomized computationmeasures of informationhardness of approximationpseudorandomnessexpander graphstime-space tradeoffshashing lemmasimperfect sources of randomness
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
