Lecture 18

Kolmogorov v Entropy and Levin's Kt complexity and universal enumeration

Lecture Notes by Ben Cousins

Lecture 17

Linear relationships between K-complexity and Entropy

Inequalities for Shannon Entropy and Kolmogorov Complexity by Daniel Hammer, Andrei Romashchenko, Alexander Shen and Nikolai Vereshchagin

Lecture Notes by Ezgi Karabulut

Lecture 16

The close relationship between H(p) and E_p(K(x)).

THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
a classic 1970 paper by Zvonkin and Levin on Kolmogorov complexity. Proposition 5.1 gives the result that in the limit K(x1...xn)/n converges to H(p) where x's are drawn independently from p.

Lecture 15

Quick Primer on Entropy

Lecture Notes by Emma Cohen

Lecture 14

Hastad Switching Lemma (cont) and Circuit Lower Bounds
Lecturer: Arefin Huq

Lecture Notes by David Durfee

Lecture 13

Kolmogorov proof of Hastad switching lemma (Part 1)

Circuit Lower Bounds à la Kolmogorov by Fortnow and Laplante

Lecture Notes by John Stewart

Lecture 12

A Kolmogorov Complexity Proof of the Lovász Local Lemma

Lecture Notes by Abhishek Banerjee

Blog Post