Papers for Presentation

Below is a list of potential papers for the presentation. Each student taking the course for credit must choose a paper to present not necessarily from the list below but must be related to Kolmogorov complexity. For the longer papers you need not read or present the whole paper.

Each student must choose a different class period to present in weeks 7-9 of the quarter (May 9-27). The presentation can be informal on the chalk board.

First come first serve.

• Power from Random Strings by Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger
• New Bounds for the Language Compression Problem by H. Buhrman, S. Laplante & P. B. Miltersen
• Possibilities and impossibilities in Kolmogorov complexity extraction by Marius Zimand
• Algorithmic Randomness and Computability by Rod Downey
• Complexity and Mixed-Strategy Equilibria by Tai-Wei Hu
• Kolmogorov's structure functions and model selection by Vereschagin and Vitanyi
• On the Complexity of Random Strings by Martin Kummer
• When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity by Eric Allender