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

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

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)

Cited In (9)

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

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)