Deterministic extractors for small-space sources

DOI10.1145/1132516.1132613zbMath1301.68193OpenAlexW2124233153MaRDI QIDQ5891932

Anup Rao, Jesse Kamp, David Zuckerman, Salil P. Vadhan

Publication date: 25 November 2014

Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: http://nrs.harvard.edu/urn-3:HUL.InstRepos:12724035

zbMATH Keywords

pseudorandomnessrandomness extractors

Mathematics Subject Classification ID

Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (9)

Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources ⋮ Extracting Computational Entropy and Learning Noisy Linear Functions ⋮ Deterministic Randomness Extraction from Generalized and Distributed Santha--Vazirani Sources ⋮ Weak derandomization of weak algorithms: explicit versions of Yao's lemma ⋮ Increasing the Output Length of Zero-Error Dispersers ⋮ Leakage-resilient coin tossing ⋮ Leakage-Resilient Coin Tossing ⋮ A Hardcore Lemma for Computational Indistinguishability: Security Amplification for Arbitrarily Weak PRGs with Optimal Stretch ⋮ Increasing the output length of zero-error dispersers

This page was built for publication: Deterministic extractors for small-space sources