Title: Derandomization and Kolmogorov Complexity
Speaker: Eric Allender, Rutgers University
Date: October 6, 2003 3:30-4:30pm
Location: DIMACS Center, CoRE Bldg, Room 433, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Kolmogorov complexity is a tool to measure the information content of strings. Strings with high Kolmogorov complexity are said to be "K-random". The study of this notion of randomness has a long history and it has close connections with the theory of computability. The set of K-random strings has long been known to be undecidable. Derandomization is a fairly recent topic in complexity theory, providing techniques whereby probabilistic algorithms can be simulated efficiently by deterministic algorithms. In this talk, I will present some new and surprising (or bizarre?) connections between these fields. In particular, we will show that everything PSPACE is poly-time reducible to the set of K-random strings, and we investigate the question of whether or not PSPACE is PRECISELY the set of decidable sets poly-time reducible to the K-random strings. This is joint work with Harry Buhrman, Michal Koucky, Dieter van Melkebeek, and Detlef Ronneburger. Some of this material was reported in our FOCS 2002 paper, but much of it is more recent. (See the paper "What is efficiently reducible to the K-random strings" on my web page.)