Extracting Kolmogorov complexity with applications to dimension zero-one laws

No abstract is available for this paper.

• Publication year

  2006

• Venue

  Information and Computation

• Publication date

  2006-07-10

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.ic.2010.09.006
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Picture codes and deciphering delay

  2017cited by this paper
• Constructive Dimension and Weak Truth-Table Degrees

  2007cited by this paper
• Extractors for a constant number of polynomially small min-entropy independent sources

  2006cited by this paper
• A lower cone in the wtt degrees of non-integral effective dimension

  2006cited by this paper
• Resource-bounded strong dimension versus resource-bounded category

  2005cited by this paper
• Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors

  2005cited by this paper
• Increasing Kolmogorov Complexity

  2005cited by this paper
• SIGACT news complexity theory column 48

  2005cited by this paper
• Extracting randomness using few independent sources

  2004influential reference
• Effective fractal dimension: foundations and applications

  2003cited by this paper
• Objective content

  2003cited by this paper
• Extractors: optimal up to constant factors

  2003cited by this paper
• Effective Strong Dimension, Algorithmic Information, and Computational Complexity

  2002cited by this paper
• A Kolmogorov complexity characterization of constructive Hausdorff dimension

  2002cited by this paper
• The dimensions of individual strings and sequences

  2002cited by this paper
• Extractors from Reed-Muller codes

  2001cited by this paper
• Simple extractors for all min-entropies and a new pseudo-random generator

  2001cited by this paper
• Extractors and pseudorandom generators

  2001cited by this paper
• Dimension in complexity classes

  2000cited by this paper
• Extracting randomness via repeated condensing

  2000cited by this paper
• Independent minimum length programs to translate between given strings

  2000cited by this paper
• Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors

  2000cited by this paper
• Extracting Randomness: A Survey and New Constructions

  1999cited by this paper
• Book Review: An introduction to Kolmogorov Complexity and its Applications Second Edition, 1997 by Ming Li and Paul Vitanyi (Springer (Graduate Text Series))

  1997cited by this paper
• Randomness-optimal oblivious sampling

  1997cited by this paper
• Randomness is Linear in Space

  1996cited by this paper
• Computing with very weak random sources

  1994cited by this paper
• An Introduction to Kolmogorov Complexity and Its Applications

  1993cited by this paper
• Almost everywhere high nonuniform complexity

  1989cited by this paper
• Unbiased bits from sources of weak randomness and probabilistic communication complexity

  1985cited by this paper
• Generating Quasi-Random Sequences from Slightly-Random Sources (Extended Abstract)

  1984cited by this paper
• Electronic Colloquium on Computational Complexity, Report No. 99 (2004) Extractors with Weak Random Seeds

  year unknowncited by this paper

• Real Numbers Equally Compressible in Every Base

  2022cites this paper
• The Algorithmic Basis of Spatial Complexity

  2020cites this paper
• Randomness and Computation

  2020influential citation
• Resource bounded randomness and its applications

  2020cites this paper
• Algorithmic randomness

  2019cites this paper
• Algorithmic Randomness Rod Downey

  2018cites this paper
• Optimal bounds for single-source Kolmogorov extractors

  2018cites this paper
• AVOIDING EFFECTIVE PACKING DIMENSION 1 BELOW ARRAY NONCOMPUTABLE C.E. DEGREES

  2018cites this paper
• Dimension 1 sequences are close to randoms

  2017cites this paper
• Mutual dimension, data processing inequalities, and randomness

  2016cites this paper
• Controlling Effective Packing Dimension of Δ02 Degrees

  2016cites this paper
• On Extracting Space-bounded Kolmogorov Complexity

  2015influential citation
• Computability theory, algorithmic randomness and Turing's anticipation

  2014cites this paper
• Some results on algorithmic randomness and computability-theoretic strength

  2014cites this paper
• Generating Kolmogorov random strings from sources with limited independence

  2013influential citation
• Shift-complex sequences

  2013cites this paper
• Short lists with short programs in short time

  2013cites this paper
• On circuit complexity classes and iterated matrix multiplication

  2012cites this paper
• Nonuniform Kolmogorov extractors

  2012cites this paper
• Symmetry of Information: A Closer Look

  2012cites this paper
• A real of strictly positive effective packing dimension that does not compute a real of effective packing dimension one

  2012cites this paper
• Space-Bounded Kolmogorov Extractors

  2012cites this paper
• Extracting information is hard: A Turing degree of non-integral effective Hausdorff dimension

  2011cites this paper
• On the Optimal Compression of Sets in PSPACE

  2011cites this paper
• Symmetry of Information and Bounds on Nonuniform Randomness Extraction via Kolmogorov Extractors

  2011cites this paper
• Possibilities and impossibilities in Kolmogorov complexity extraction

  2011cites this paper
• Kolmogorov Complexity in Randomness Extraction

  2011influential citation
• Impossibility of Independence Amplification in Kolmogorov Complexity Theory

  2010cites this paper
• SIGACT news complexity theory column 68

  2010cites this paper
• Combinatorial characterizations of extractors and Kolmogorov extractors

  2010cites this paper
• Counting Dependent and Independent Strings

  2010cites this paper
• Effective Packing Dimension and Traceability

  2010cites this paper
• On Generating Independent Random Strings

  2009cites this paper
• Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence

  2009cites this paper
• Constructive Dimension and Weak Truth-Table Degrees

  2007cites this paper
• Constructive Dimension and Turing Degrees

  2007influential citation
• Two Sources Are Better than One for Increasing the Kolmogorov Complexity of Infinite Sequences

  2007influential citation
• Dimension Extractors

  2006cites this paper
• Dimension Extractors and Optimal Decompression

  2006influential citation
• Pushdown dimension

  2005cites this paper
• Effective fractal dimension: foundations and applications

  2003cites this paper