from Hacker News

Kolmogorov Complexity – A Primer (2012)

by poindontcare on 10/2/16, 4:16 AM with 20 comments

• by cosmoharrigan on 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 sn41 on 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 mherrmann on 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 cosmoharrigan on 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 cosmoharrigan on 10/2/16, 8:13 AM

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

• by woliveirajr on 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 eveningcoffee on 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-Sendai on 10/2/16, 1:00 PM

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