An introduction to Kolmogorov complexity and its applications
by Ming Li, Paul Vitanyi · first published 1993
50% recommend50% neutral
Why HN recommends it
The standard reference on Kolmogorov complexity, covering its theory and applications. It offers a rigorous treatment of the subject, going beyond popular overviews.
Summarised by Claude from recommending comments
Written by two experts in the field, this book is ideal for advanced undergraduate students, graduate students, and researchers in computer science, mathematics, cognitive sciences, philosophy, artificial intelligence, statistics, and physics. It 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, as well as a great deal of new material not included in the first edition.
Affiliate links. As an Amazon Associate I earn from qualifying purchases.
…Dasgupta-Papadimitriou-Vazirani; Cormen-Leisersen-Rivest-Stein; Kleinberg-Tardos; and more. A bit farther from core CS, I also like: - Cover, Thomas. Elements of Information Theory. - Li, Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications
on “Ask HN: What are the most fundamental books on computer science?” ↗do you have any resources that are more rigorous? For light bedtime reading, there's An Introduction to Kolmogorov Complexity and Its Applications: http://www.amazon.com/Introduction-Kolmogorov-Complexity-App... That is, the laws of thermodynamics concisely phrase the increasing entropy of the universe with a low Komolgorov complexity, suggesting…
on “Razoring Ockham’s Razor” ↗…lunch: The trick you use to bring down the Kolgomorov complexity K(L, S) down to 0 increases the complexity of L. This can be taken into account, see "conditional Kolgomorov complexity". The book "An Introduction to Kolmogorov Complexity and Its Applications" by Li and Vitányi explains this, and much more in great detail, and is highly recommended.
on “Doing Mathematics Differently” ↗The standard reference is "An Introduction to Kolmogorov Complexity and Its Applications", from Ming Li and Paul Vitányi. It is the "must-go" for the subject. An introductory chapter is available in the "Elements of Information Theory" of Thomas Cover and Joy Thomas. The field is called…
on “Kolmogorov Complexity (2014) [pdf]” ↗Thanks for the video, I will watch it. The interested readers might want to try the book "An Introduction to Kolmogorov Complexity and its Applications" by Li and Vitanyi (the 3rd edition came out recently). It is comparatively expensive, but Vitanyi's CWI site holds additional material.
on “Elegant Lisp programs” ↗Sipser's undergraduate textbook on the theory of computation[1] has a single, very nice, introductory chapter on the topic. If you want to get technical and deep, you probably want [2] (An introduction to Kolmogorov complexity and its applications). It's pretty hard, though. Not for the faint of heart. [1] http://www.amazon.com/Introduction-Theory-Computation-Michae... [2] http://www.amazon.com/Introduction-Kolmogorov-Complexity-App...
on “Kolmogorov Complexity (2014) [pdf]” ↗…35. The Bayesian Choice - Christian P. Robert 35. Machine Learning for Commonsense Reasoning Processes - Xenia Naidenova 36. Reinforcement Learning and Optimal Control - Dimitri P. Bertsekas 37. An Introduction to Kolmogorov Complexity and Its Applications - Ming Li & Paul Vitanyi 38. The Mechanical Mind: A Philosophical Introduction to Minds, Machines, and Mental Representation - Tim Crane 39. Constraining Cognitive Theories - Zenon W. Pylyshyn 40.…
on “Ask HN: What projects are you working on now?” ↗…use normalized compression distance (NCD). NCD is a way to approximate Kolmogorov complexity. This is a pretty old idea, see [1,2]. Old but still very useful, like perceptrons. [1] Li and Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications. [2] Clustering by compression. https://arxiv.org/pdf/cs/0312044
on “Gzip and KNN Outperforms Transformers on Text Classification” ↗See "Logical Depth" as defined by Charles Bennett: http://researcher.ibm.com/researcher/files/us-bennetc/UTMX.p... as well as Chapter 7, "Resource-Bounded Complexity", from "An introduction to Kolmogorov complexity and its applications".
on “Kolmogorov Complexity – A Primer (2012)” ↗Thanks, I had to dig. I read about it in [1]. Mises was concerned about the formalization of probability theory. It seems the idea appears at least as early as in his 1919 paper [2]. [1] An Introduction to Kolmogorov Complexity and Its Applications, M. Li & P. Vitnányi [2] Grundlagen der Wahrscheinlichkeitsrechnung, R. von Mises
on “Kolmogorov Complexity and Compression Distance (2023)” ↗