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.