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

DOI10.1137/060671218zbMath1185.68453OpenAlexW2022435843MaRDI QIDQ5189543

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

Ramsey graphsextractorindependent sources

Mathematics Subject Classification ID

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

Related Items (13)

Zero-Fixing Extractors for Sub-Logarithmic Entropy ⋮ Local Correlation Breakers and Applications to Three-Source Extractors and Mergers ⋮ An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy ⋮ 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction ⋮ Deterministic Randomness Extraction from Generalized and Distributed Santha--Vazirani Sources ⋮ Unnamed Item ⋮ An Introduction to Randomness Extractors ⋮ Extractor Lower Bounds, Revisited ⋮ Extractors and Lower Bounds for Locally Samplable Sources ⋮ 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 ⋮ Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs

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