DIMACS Theoretical Computer Science Seminar

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


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