Login
Computer Science @ Rochester
Monday, November 07, 2005
11:00 AM
CSB 209
Lance Fortnow
U. Chicago
Connections between Kolmogorov and Computational Complexity
We describe a couple of results showing some close connections between Kolmogorov complexity and computational complexity.

1) Levin considers the distribution m(x)=2^-K(x) and shows that m(x) is universal among the semicomputable semimeasures. We consider the polynomial-time version of this distribution m^p(x) and under a reasonable derandomization assumption we show that m^p(x) is universal among the polynomial-time sampleable distributions.

2) We use recent results on constructible extractors to show how to efficiently produce random strings from longer strings with some randomness. We show some application to zero-one laws for the strong dimension of E in ESPACE.

The first result is joint work with Luis Antunes, the second with John Hitchcock, Aduri Pavan, N. V. Vinodchandran and Fengming Wang.