A BRICS Mini-Course
August 17 and 18, 2004
Lectures by
Eric Allender, allender@cs.rutgers.edu
Department of Computer Science, Rutgers, the State University of NJ
For nearly four decades, Kolmogorov complexity has been studied as a tool for measuring the information content of strings. Among other applications, Kolmogorov complexity provides a precise mathematical definition of "randomness". Kolmogorov complexity has close connections with the theory of computability; the set of Kolmogorov-random strings has long been known to be undecidable.
In contrast, derandomization is a fairly recent topic in complexity theory, providing techniques whereby probabilistic algorithms can be simulated efficiently by deterministic algorithms.
This mini-course will survey some recently-discovered connections between the fields of Kolmogorov complexity theory, circuit complexity, and derandomization. We will see how resource-bounded Kolmogorov complexity provides natural examples of sets that are complete for various complexity classes under certain types of reducibility, that are provably not complete under some other types of reduction. We will also show that, in some cases, it is possible to characterize complexity classes in terms of efficient reducibility to the (undecidable) set of Kolmogorov-random strings.
The mini-course will highlight numerous open problems that seem to be promising directions for additional research.