[Computational Complexity] Randomness in Madison
- I'm at the University of Wisconsin for the second FRG Workshop on Algorithmic Randomness. FRG stands for "Focused Research Group", in our case a 12 PI NSF-funded project to study the properties or random reals, essentially Kolmogorov complexity on infinite strings. Most of the PIs are logicians from the computability theory community but a handful of us (Eric Allender, John Hitchcock, Jack Lutz and myself) have a computational complexity background. The workshop draws well beyond the PIs including foreign researchers and students.Both the deep theory and connections of algorithmic randomness to other research areas (such as expert algorithms, extractors, measure theory and Hausdorff dimension) has grown tremendously in the past several years. The Kellogg business school at Northwestern just hired a new assistant professor Tai-Wei Hu from Penn State Econ whose job talk paper applies algorithmic randomness that he learned in a logic class from Steve Simpson to understand probability in repeated games.I've only seen one talk here so far but it was a good one: Alexander Shen showed how to convert many basic questions about Kolmogorov complexity into who wins a certain kind of game.Unfortunately because of teaching and STOC, I won't be at the workshop long. I've giving a short talk here tomorrow that doesn't directly relate to the topic at hand but kind of a cute not too difficult result: There is a computable enumerable, non-computable oracle A, such that PA-P has no computable sets. Ponder it and I'll post the proof someday when I get it written up.
Posted By Lance to Computational Complexity at 5/28/2009 07:16:00 AM