CS Colloquium on Oct. 8 at 11am

Title: Derandomization and Kolmogorov Complexity

Speaker: Eric Allender, Rutgers University
         http://athos.rutgers.edu/~allender/

Date: October 8 (Wednesday)
Time: 11am 
Place: MCS 135

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.

Biography of the Speaker:

Eric Allender received his Ph.D. from Georgia Tech in 1985, and has been a
faculty member at Rutgers University ever since, with brief visiting
positions at Princeton, Wuerzburg, Tuebingen, and the Institute of
Mathematical Sciences in Madras, India.

Prof. Allender is the author of many papers in field of computational
complexity theory; he has done work on circuit complexity, on Kolmogorov
complexity, and on complexity classes.  He has given numerous invited
addresses at computer science symposia worldwide.  He succeeded Juris
Hartmanis as the editor of the Computational Complexity Column for the
Bulletin of the European Association for Theoretical Computer Science, and
for three years he chaired the Steering Committee for the annual IEEE
Conference on Computational Complexity (succeeding Steve Homer in this
position).  He serves on the Scientific Board for the Electronic Colloquium
on Computational Complexity (ECCC).

Host: Steve Homer (http://www.cs.bu.edu/~homer)