Dieter van Melkebeek(University of Wisconsin, Madison):
Power from Random Strings

The notion of a random string has two well-established meanings in theoretical computer science: a probabilistic one, and a descriptive one. In algorithmic applications, random strings are defined in terms of probability distributions. In Kolmogorov complexity, a string is considered random if it does not have a short description.

The relationship between both notions plays a crucial role in the area of pseudo-randomness and derandomization. Using these relationships, we obtain hardness results for the set of descriptively random strings (for various Kolmogorov measures). Previously, it was believed that these sets did not have enough structure to capture the power of the complexity classes they naturally live in. In contrast, we show that they *are* complete for these classes.

Joint work with Allender, Buhrman, Koucky, and Ronneburger, to be presented at FOCS 2002.