Lecture 15

Introduction to Entropy and Linear Inequalities of Entropy and Kolmogorov Complexity

Scribe Notes by Aleck Johnsen

Daniel Hammer, Andrei Romashchenko, Alexander Shen, Nikolai Vereshchagin, Inequalities for Shannon Entropy and Kolmogorov Complexity, Journal of Computer and System Sciences, Volume 60, Issue 2, April 2000, Pages 442-464.

Lecture 14

Switching Lemma and Application to Parity

Scribe Notes by Kai Hayashi

Lecture 13

Switching Lemma Continued

Lecture 12

Proof of constructive LLL. Overview of Circuit Complexity and Switching Lemma.

L. Fortnow and S. Laplante. Circuit lower bounds a la Kolmogorov. Information and Compuation, 123(1):121-126, 1995.


Scribe Notes by Arefin Huq

Lecture 11

Instructions for Paper Presentations

The incompressibility method: Ramsey's Theorem and Lovász Local Lemma

Blog Post on LLL

Lecture 10

K(x) as universal measure. Worst = Average Case on universal measure.

Scribe Notes by Darrel Hoy

Lecture 9

2^-K(x) as a universal lower-semi-computable semi-measure

Scribe Notes by Aleck Johnsen

Lecture 8

Chaitin's Omega, Lower Semi-Computable Semi-Measures

Scribe notes by Sam Carton

Lecture 7

Basic Properties of Prefix-Free K complexity

Scribe Notes by Arefin Huq

Lecture 6

Random Strings are hard for the halting problem. Start of Prefix-free complexity.

Scribe Notes by Kai Hayashi 

Lecture 5

Properties of C

Scribe Notes by Aleck Johnsen

Lecture 4

Statistical Properties of Random Strings, C as a function from integers to integers

Scribe Notes by Sam Carton

Lecture 3

k-random strings, symmetry of information and an application to logic

Scribe Notes by Fred Robertson

Richard Lipton post on random axioms