Deterministic extractors for small-space sources

DOI10.1145/1132516.1132613MaRDI QIDQ5891932zbMATH OpenOpenAlexFDO

Authors Jesse Kamp, Anup Rao, David Zuckerman, Salil 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

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

Recommendations

• Deterministic extractors for small-space sources
• Deterministic Extractors for Independent-Symbol Sources
• Deterministic Extractors for Bit‐Fixing Sources by Obtaining an Independent Seed
• How to get more mileage from randomness extractors
• Extractors for circuit sources

Cited in

(17)

• Leakage-resilient coin tossing
• Deterministic randomness extraction from generalized and distributed Santha-Vazirani sources
• Leakage-Resilient Coin Tossing
• Increasing the output length of zero-error dispersers
• Extractors for Turing-machine sources
• A Hardcore Lemma for Computational Indistinguishability: Security Amplification for Arbitrarily Weak PRGs with Optimal Stretch
• Deterministic randomness extraction from generalized and distributed Santha-Vazirani sources
• Increasing the Output Length of Zero-Error Dispersers
• Extractors
• Deterministic Extractors for Independent-Symbol Sources
• Weak derandomization of weak algorithms: explicit versions of Yao's lemma
• Extractors for weak random sources and their applications
• Extractors for a Constant Number of Polynomially Small Min-Entropy Independent Sources
• Extracting Computational Entropy and Learning Noisy Linear Functions
• Deterministic extractors for small-space sources
• Almost Chor-Goldreich sources and adversarial random walks
• Efficient randomized strong 2-source non-malleable extractor for any linear min-entropy

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5891932)