Kolmogorov complexity in randomness extraction

DOI10.4230/LIPICS.FSTTCS.2009.2320zbMATH Open1248.68268OpenAlexW2243799055MaRDI QIDQ2920128FDOQ2920128

Authors John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran

Publication date 24 October 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_4680.html

zbMATH Keywords

randomnessextractorsKolmogorov extractors

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Kolmogorov complexity in randomness extraction
• Optimal bounds for single-source Kolmogorov extractors
• Space-bounded Kolmogorov extractors
• On extracting space-bounded Kolmogorov complexity
• Extracting Kolmogorov complexity with applications to dimension zero-one laws

Cited in

(12)

• On extracting space-bounded Kolmogorov complexity
• Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws
• Kolmogorov Complexity and Algorithmic Randomness
• On the optimal compression of sets in PSPACE
• Randomness extraction in computability theory
• Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence
• Kolmogorov complexity in randomness extraction
• Impossibility of independence amplification in Kolmogorov complexity theory
• Extracting Kolmogorov complexity with applications to dimension zero-one laws
• Symmetry of Information: A Closer Look
• Optimal bounds for single-source Kolmogorov extractors
• Space-bounded Kolmogorov extractors

This page was built for publication: Kolmogorov complexity in randomness extraction

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