A Short Introduction to Kolmogorov Complexity

Theory of statistical estimation

R.A. Fisher · 1925

Earlier work this paper cites.

On computable numbers with an application to the Entscheidungsproblem

Alan M. Turing · 1936

Earlier work this paper cites.

A mathematical theory of communication

Claude E. Shannon · 1948

Earlier work this paper cites.

A formal theory of inductive inference, part 1 and part 2

Ray Solomonoff · 1964

Earlier work this paper cites.

Three approaches to the quantitative definition of information

Andrei Nikolaevich Kolmogorov · 1965

Cited alongside, same era.

On the length of programs for computing finite binary sequences

Gregory J. Chaitin · 1966

Cited alongside, same era.

On the length of programs for computing finite binary sequences: statistical considerations

Gregory J. Chaitin · 1969

Cited alongside, same era.

Laws of information conservation (non-growth) and aspects of the foundation of probability theory

L.A. Levin · 1974

Cited alongside, same era.

Elements of Information Theory

Thomas M. Cover and Joy A. Thomas · 1991

Later among the works it cites.

An Introduction to Kolmogorov Complexity and Its Applications

Ming Li and Paul Vitányi · 1997

Later among the works it cites.

Kolmogorov’s Structure Functions with an Application to the Foundations of Model Selection

Original

Nikolai Vereshchagin and Paul Vitányi · 2002

Later among the works it cites.

The Paradox of Overfitting

Volker Nannen · 2003

Later among the works it cites.