An introduction to Kolmogorov complexity and its applications
Springer, 2008. [All Versions]. The introductory book for Algorithmic Information Theory, especially the Kolmogorov complexity theory.
- from
- AGI & CoCoSci
- added
- 2026-10-10
- likes
- 0
similar
-
The KoLMogorov Test: Compression by Code Generation openreview.net
ICLR'25, 2025. [All Versions]. Compression is at the heart of intelligence. A theoretically optimal way to compress any sequence of data is to find the shortest program that outputs that sequence and then halts. However, such Kolmogorov compression is uncomputable, and code…
-
Algorithmic Information Theory ieeexplore.ieee.org
IBM Journal of Research and Development, 1977. [All Versions]. Chaitin's original paper on Algorithmic Information Theory.
-
Rao & Yehudayoff. Communication Complexity and Applications cambridge.org
An excellent and very readable introductory textbook to the field of communication complexity.
-
Ogihara & Hemaspaandra. The Complexity Theory Companion springer.com
An accessible, algorithmically oriented, research-centered, up-to-date guide to some of the most interesting techniques of complexity theory.
-
Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity mitpress.mit.edu
A complete comprehensive encyclopediac handbook which surveys all related areas to theoretical computer science.
-
Sipser. Introduction to Theory of Computation cengage.com
A standard text for introducing theory of computation for undergrads.
AGI & CoCoSci › Papers > Complexity & Information Theory > Theory: “Springer, 2008. [All Versions]. The introductory book for Algorithmic Information Theory, especially the Kolmogorov complexity theory.”