An Introduction to Kolmogorov Complexity and Its Applications

By Ming Li, Paul M. B. Vitányi. 1993

The book is outstanding and admirable in many respects. ... is necessary reading for all kinds of readers from undergraduate students to top authorities in the field. Journal of Symbolic Logic Written by two experts in the field, this is the only comprehensive and unified treatment of the central ideas and their applications of Kolmogorov complexity. The book presents a thorough treatment of the subject with a wide range of illustrative applications. Such applications include the randomness of finite objects or infinite sequences, Martin-Loef tests for randomness, information theory, computational learning theory, the complexity of algorithms, and the thermodynamics of computing. It will be ideal for advanced undergraduate students, graduate students, and researchers in computer science, mathematics, cognitive sciences, philosophy, artificial intelligence, statistics, and physics. The book is self-contained in that it contains the basic requirements from mathematics and computer science. Included are also numerous problem sets, comments, source references, and hints to solutions of problems. New topics in this edition include Omega numbers, KolmogorovLoveland randomness, universal learning, communication complexity, Kolmogorov's random graphs, time-limited universal distribution, Shannon information and others.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Deep learning in neural networks: An overview (2014, neutral): “Most FNN applications focused on FNNs with few hidden layers.”
Generalization in anti-causal learning (2018, neutral): “” (6)The Kolmogorov complexity of an object is the shortest program on a given universal Turing machine that outputs the object, see (Li and Vitányi, 2008) for an overview.”
Causal Inference Using the Algorithmic Markov Condition (2008, neutral): “Here, observables denote something in the real world that can be observed and the observation of which can be formalized in terms of a mathematical language.”
Optimal Ordered Problem Solver (2002, neutral): “At ﬁrst naive glance this seems unlikely, since it has been well-known for many decades that most possible pairs of symbol strings (such as problem-solving programs) do not share any algorithmic information; e.g., Li and Vit´anyi (1997).”
Compress and Control (2014, positive): “This class of methods can be formally justified by appealing to various notions within algorithmic information theory, such as Kolmogorov complexity (Li and Vitányi 2008).”
Self-Delimiting Neural Networks (2012, positive): “…more principled SLIM NNs can learn to actively select in task-speciﬁc ways their own size, that is, their effective number of weights ( = modiﬁable free parameters), in line with the theory of algorithmic probability and optimal universal inductive inference [71, 34, 54, 43, 55, 56, 57, 30].”
Goedel Machines: Self-Referential Universal Problem Solvers Making Provably Optimal Self-Improvements (2003, unknown): “P(w) could be based on program length, e.g., P(w) = 2 l(w) for binary programs w [23, 25 ], or on a probabilistic”
Planning algorithms (2006, unknown): “As long as the instance encoding is within a polynomial factor of the optimal encoding (this can be made precise using Kolmogorov complexity [633]), then this bizarre behavior is avoided.”
TSclust: An R Package for Time Series Clustering (2014, unknown): “The Kolmogorov complexity K ( x ) of an object x is the length of the shortest program capable to produce x on a universal computer, such as a Turing machine (Li and Vit´anyi 2007).”
Probabilistic Incremental Program Evolution (1997, unknown): “The EFs are exploited in an on-line fashion to learn rewarding action sequences (Whitehead & Ballard, 1990; Schmidhuber, 1991; Chrisman, 1992; Lin, 1993; Clii & Ross, 1994; Ring, 1995; McCallum, 1996; Wiering & Schmidhuber, 1996a).”
Bayesian Model Estimation and Selection for Epipolar Geometry and Generic Manifold Fitting (2002, unknown): “The complexity of the data together with the model is simply the Kologmorov complexity (Li and Vit´anyi, 1997) (being the length of the shortest Turing machine to encode the data and model), which can be used to derive a prior on models based on complexity (amount of non-randomness).”