DIMACS Discrete Math/Theory of Computing Seminar

Title: Power from Random Strings

Speaker: Detlef Ronneburger, Rutgers University

Date: Tuesday, December 10, 4:30 PM

Location: CoRE Building, room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

In this talk we consider sets that only contain Kolmogorov-random strings, i.e. strings x, where we need a description of length, say, at least |x|/2 to generate x with a (possibly resource bounded) Turing machine.

These types of sets don't seem to have a clear structure and thus are usually not considered to be suitable as complete sets for different complexity classes. In fact, for some of these sets it was previously shown [BM97, All01] that they are not hard for the classes they reside in under deterministic, uniform reductions.

On the other hand, in [BT01] it was shown that the set of strings with high Space bounded conditional Kolmogorov complexity is complete for PSPACE under nondeterministic Turing reductions.

Using different techniques we will argue that sets of strings of high appropriate resource bounded Kolmogorov (e.g. using Levin's notion of Kt complexity) are complete for EXP (or respectively PSPACE) under P/Poly and NP - reductions. Our proof techniques heavy rely on results in derandomization.

Time permitting we will investigate how relations between different notions of resource bounden Kolmogorov complexity translate into relations between different complexity classes.