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!