Lecture 22

Computational Depth Continued

Scribe Notes by Kai Hayashi

L. Antunes, L. Fortnow, A. Pinto, and A. Souto. Low-depth witnesses are easy to find. In Proceedings of the 22nd IEEE Conference on Computational Complexity, pages 46-51. IEEE, New York, 2007.


L. Antunes and L. Fortnow. Worst-case running times for average-case algorithms. In Proceedings of the 24th IEEE Conference on Computational Complexity, pages 298-303. IEEE, 2009. 

Lecture 21

Equivalence of MDL, Kolmogorov Structure Function and Best Fit

Intro to Computational Depth

Scribe Notes by Aleck Johnsen

L. Antunes, L. Fortnow, D. van Melkebeek, and N. Vinodchandran. Computational depth: Concept and applications. Theoretical Computer Science, 354(3):391-404, April 2006.

Lecture 20

Prediction using universal measure.

Scribe notes from Federick Robinson.

Student Presentations

• Wednesday, May 11: On the Complexity of Random Strings by Martin Kummer (Michael Wurtz)
• Friday, May 13: Power from Random Strings by Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger (Arefin Huq)
• Monday, May 16: Complexity and Mixed-Strategy Equilibria by Tai-Wei Hu (Kai Hayashi)
• Wednesday, May 18: New Bounds for the Language Compression Problem by H. Buhrman, S. Laplante & P. B. Miltersen (Darrel Hoy)
• Friday, May 20: Possibilities and impossibilities in Kolmogorov complexity extraction by Marius Zimand (Frank Robinson)
• Monday, May 23: On Initial Segment Complexity and Degrees of Randomness, J. Miller and L. Yu (Aleck Johnsen)
• Wednesday, May 25: When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity by Eric Allender (Sam Carton)

Lecture 19

C^t and CD^t complexity. Bounding sizes of sets with CD complexity.

Lecture 18

Levin's Kt complexity and universal search

Scribe Notes by Arefin Huq

N. Devanur and L. Fortnow. A computational theory of awareness and decision making. In Proceedings of the 12th Conference on Theoretical Aspects of Rationality and Knowledge, pages 99-107. ACM, 2009.

Lecture 17

Inequalities for entropy hold for K-complexity. Time-bounded complexity

Happy 40th to P versus NP!

Lecture 16

Linear inequalities for K-complexity imply linear inequalities for Entropy.

Scribe Notes by Darrell Hoy.

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

Lecture 2

Basic properties of K-complexity. Using K-complexity to analyze prime numbers.

Scribe Notes by Michael Wurtz

Lecture 1

What is randomness? The basic definitions and properties of Kolmogorov complexity.

Kolmogorov Complexity by Lance Fortnow. Notes from a 2000 New Zealand Summer School.


Scribe Notes by Darrell Hoy

Course Information

EECS 395/495-0-20: Kolmogorov Complexity

Spring 2011

Lecturer: Lance Fortnow

Lectures: MWF 9:00-9:50 in Tech LG68

Description:

This course will study the Kolmogorov complexity of finite strings which measures the information content (or randomness) of a string by the size of the smallest program that generates it. This simple idea has a surprisingly deep theory with many exciting applications to logic and computer science. We cover the basic relationships of Kolmogorov complexity, applications with an emphasis in connections with computational complexity. Topics include: Basic Properties of the Kolmogorov function, Symmetry of Information, The Incompressibility Method, Resource-Bounded complexity, and applications to circuit complexity and randomized constructions.

This course is designed for graduate students or advanced undergraduates. We will assume familiarity with mathematical proofs but no previous knowledge of Turing machines or computational complexity.

Textbook: An Introduction to Kolmogorov Complexity and Its Applications by Ming Li and Paul Vitanyi.