Extractors for a Constant Number of Polynomially Small Min-Entropy Independent Sources

DOI10.1137/060671218MaRDI QIDQ5189543zbMATH OpenOpenAlexFDO

Authors Anup Rao

Publication date 17 March 2010

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

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

zbMATH Keywords

extractorindependent sourcesRamsey graphs

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Graph theory (including graph drawing) in computer science (68R10) Measures of information, entropy (94A17)

Recommendations

• Extractors for a constant number of polynomially small MIN-entropy independent sources
• An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy
• An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy
• An explicit two-source extractor with min-entropy rate near $4/9$
• Deterministic Extractors for Independent-Symbol Sources
• Deterministic Extractors for Independent-Symbol Sources
• An Entropy Lower Bound for Non-Malleable Extractors
• Deterministic extractors for small-space sources
• Deterministic extractors for small-space sources
• Zero-fixing extractors for sub-logarithmic entropy

Cited in

(19)

• 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction
• How to extract useful randomness from unreliable sources
• Explicit two-source extractors and resilient functions
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• Extractors for a constant number of polynomially small MIN-entropy independent sources
• Deterministic randomness extraction from generalized and distributed Santha-Vazirani sources
• An introduction to randomness extractors
• Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic
• Local correlation breakers and applications to three-source extractors and mergers
• Zero-fixing extractors for sub-logarithmic entropy
• Extractors for Three Uneven-Length Sources
• An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy
• Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs
• An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy
• Extractors for sumset sources
• New independent source extractors with exponential improvement
• scientific article; zbMATH DE number 7650110 (Why is no real title available?)
• Extractors and lower bounds for locally samplable sources
• Extractor Lower Bounds, Revisited

This page was built for publication: Extractors for a Constant Number of Polynomially Small Min-Entropy Independent Sources

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