This episode breaks down the 'Kolmogorov Complexity' paper, which discusses the fascinating topic of algorithmic information theory, which explores the inherent complexity of representing information using algorithms. It defines Kolmogorov complexity, a measure of the shortest computer program needed to describe a piece of data. The text then examines various related concepts like conditional complexity, prefix complexity, and monotone complexity, ultimately exploring their connections with algorithmic randomness. It delves into the nature of random sequences, contrasting computable randomness with the more intuitive Mises-Church randomness, and analyses the impact of selection rules on randomness. The chapter also explores relationships between entropy, complexity, and size and offers insights into multisource information theory and algorithmic statistics.

Audio : (Spotify) https://open.spotify.com/episode/1EhNcxqkmGE7uVLhs583DL?si=OgDArRDTQ0mHF-O1j-Jwkg

Paper: https://www.lirmm.fr/~ashen/kolmbook-eng-scan.pdf