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.