Extracting Kolmogorov complexity with applications to dimension zero-one laws

DOI10.1016/j.ic.2010.09.006zbMath1215.68114OpenAlexW2136421483MaRDI QIDQ716318

N. V. Vinodchandran, A. Pavan, John M. Hitchcock, Fengming Wang, Lance J. Fortnow

Publication date: 28 April 2011

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2010.09.006

zbMATH Keywords

Kolmogorov complexityESPACEKolmogorov-randomness

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic randomness and dimension (03D32)

Related Items (4)

Shift-complex sequences ⋮ Dimension 1 sequences are close to randoms ⋮ Short lists with short programs in short time ⋮ On extracting space-bounded Kolmogorov complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension
• Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences
• Resource-bounded strong dimension versus resource-bounded category
• Extracting randomness: A survey and new constructions
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• The dimensions of individual strings and sequences
• Randomness is linear in space
• Extractors from Reed-Muller codes
• Kolmogorov Complexity in Randomness Extraction.
• Extractors for a constant number of polynomially small min-entropy independent sources
• Randomness and Computability: Open Questions
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• On Generating Independent Random Strings
• Extractors
• Extractors with weak random seeds
• Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws
• Computing with Very Weak Random Sources
• Dimension in Complexity Classes
• Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence
• Constructive Dimension and Weak Truth-Table Degrees
• Extractors and pseudorandom generators
• Extracting Randomness via Repeated Condensing
• STACS 2005
• Simulating independence
• Independent minimum length programs to translate between given strings

This page was built for publication: Extracting Kolmogorov complexity with applications to dimension zero-one laws