An introduction to Kolmogorov - complexity and its applications ; part 1: theory

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

How researchers see this paper

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

1. Xin Chen
2. Ming Li
3. Brent Francia
4. Michael Mampaey
5. Brian McKinnon
6. Amit Seker
7. Jilles Vreeken
8. Aaron D. Lanterman

Citations in the corpus

• Shared information and program plagiarism detection (2004, methodology): “1 Its definition is based on Kolmogorov complexity or algorithmic entropy [9].”
• Summarizing categorical data by clustering attributes (2011, background): “3.1 MDL, a brief primer The MDL (Minimum Description Length) principle (Rissanen, 1978), like its close cousin MML (Minimum Message Length) (Wallace, 2005), is a practical version of Kolmogorov Complexity (Li and Vitányi, 1993).”
• Schwarz, Wallace, and Rissanen: Intertwining Themes in Theories of Model Selection (2001, methodology): “A profound theorem, proved independently by Kolmogorov, Chaitin, and Solomonoff (Li & Vitányi, 1997), asserts that there is no algorithm which can find the shortest computer program to reproduce a particular set of data, or even find the length of such a shortest program.”