Oct 6:     Derandomization and Kolmogorov Complexity
                                     Eric Allender .

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.)

--------