An introduction to Kolmogorov complexity and its applications

DOI10.1007/978-3-030-11298-1zbMath1423.68005OpenAlexW1638203394MaRDI QIDQ5915950

Paul M. B. Vitányi, Ming Li

Publication date: 15 February 2019

Published in: Texts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-11298-1

zbMATH Keywords

computational complexityalgorithmic information theorydata compressionKolmogorov complexitycomputational learninginstance complexitycircuit theoryinductive reasoninguniversal predictionCD compressiondistributed algorithmicsfoundations of statistical methods in physicsKolmogorov random graphsshortest encoding

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Research exposition (monographs, survey articles) pertaining to computer science (68-02)

Related Items (31)

Quantum information distance ⋮ The Normalized Algorithmic Information Distance Can Not Be Approximated ⋮ The Whole and the Parts: The Minimum Description Length Principle and the A-Contrario Framework ⋮ Weak measurements and nonclassical correlations ⋮ Entanglement, complexity, and causal asymmetry in quantum theories ⋮ On continued fraction randomness and normality ⋮ Bayesian definition of random sequences with respect to conditional probabilities ⋮ Extending the reach of the point-to-set principle ⋮ Approximating Kolmogorov complexity ⋮ Martingales in the Study of Randomness ⋮ The Kučera-Gács theorem revisited by Levin ⋮ Distributed computing with the Cloud ⋮ Fiducialize statistical significance: transformingp-values into conservative posterior probabilities and Bayes factors ⋮ Absolutely no free lunches! ⋮ Proofs of conservation inequalities for Levin's notion of mutual information of 1974 ⋮ Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity ⋮ Bi-immunity over different size alphabets ⋮ A new quantum random number generator certified by value indefiniteness ⋮ Unnamed Item ⋮ Mathematics as information compression via the matching and unification of patterns ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization ⋮ A theory of incremental compression ⋮ Randomness and Effective Dimension of Continued Fractions. ⋮ Algorithmic information dynamics of cellular automata ⋮ Irregular \(\mathcal{B}\)-free Toeplitz sequences via Besicovitch's construction of sets of multiples without density ⋮ Application of minimum description length criterion to assess the complexity of models in mathematical immunology ⋮ Thinking with notations: epistemic actions and epistemic activities in mathematical practice ⋮ On trees without hyperimmune branches ⋮ Deterministic and nondeterministic iterated uniform finite-state transducers: computational and descriptional power ⋮ PAC-learning gains of Turing machines over circuits and neural networks ⋮ Computable Measure Theory and Algorithmic Randomness

This page was built for publication: An introduction to Kolmogorov complexity and its applications