Kolmogorov complexity in randomness extraction

DOI10.4230/LIPICS.FSTTCS.2009.2320MaRDI QIDQ2920128zbMATH OpenOpenAlexFDO

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)

• 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
• Space-bounded Kolmogorov extractors
• Kolmogorov complexity in randomness extraction
• On the optimal compression of sets in PSPACE
• Symmetry of Information: A Closer Look
• Randomness extraction in computability theory
• Optimal bounds for single-source 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)