Kolmogorov Complexity – A Primer (2012)

by poindontcareon 10/2/16, 4:16 AMwith 20 comments
by cosmoharriganon 10/2/16, 8:14 AM

An extremely detailed treatment is presented in "An introduction to Kolmogorov complexity and its applications": http://www-2.dc.uba.ar/materias/azar/bibliografia/LiVitanyi1...

by sn41on 10/2/16, 10:28 AM

There are a lot of good recent books on this topic (I don't know if this area is undergoing a revival) :

1. N. K. Vereschagin, V. Uspensky, Alexander Shen : Kolmogorov Complexity (English draft in preparation: http://www.lirmm.fr/~ashen/kolmbook-eng.pdf)

2. Downey, Hirschfeldt: Algorithmic Randomness and Complexity (http://www.springer.com/gp/book/9780387955674)

3. Andre Nies: Computability and Randomness (https://global.oup.com/academic/product/computability-and-ra...)

in addition to the now classic book by Li and Vitanyi that others have mentioned.

by mherrmannon 10/2/16, 8:13 AM

When two strings have the same Kolmogorov Complexity, one of them might take significantly longer to "decompress". Shouldn't we then say that this string has higher information content?

It feels to me like Kolmogorov Complexity (while very elegant) might just be a crude approximation to a measure that also takes into account the time it takes to print the string.

by cosmoharriganon 10/2/16, 8:06 AM

Kolmogorov Complexity is also presented in Chapter 7 of the classic textbook "Elements of Information Theory": http://poincare.matf.bg.ac.rs/nastavno/viktor/Kolmogorov_Com...

by cosmoharriganon 10/2/16, 8:13 AM

An overview with additional references from Marcus Hutter: http://www.scholarpedia.org/article/Algorithmic_complexity

by woliveirajron 10/3/16, 1:30 AM

I've used it (by using Normalized Compression Distance) in my Master degree.

It was very interesting to find out how efficient it was in authorship attribution, even having 100 possible authors.

by eveningcoffeeon 10/2/16, 9:13 AM

Linux dev/random entropy quality check is (was, I have not checked it recently) based on Kolmogorov complexity.

by Ono-Sendaion 10/2/16, 1:00 PM

If we're doing Kolmogorov complexity reposts: http://forwardscattering.org/post/7 http://forwardscattering.org/post/14