Derandomizing from Random Strings

Original · EN

In this paper we show that BPP is truth-table reducible to the set of Kolmogorov random strings Rₖ. It was previously known that PSPACE, and hence BPP is Turing-reducible to Rₖ. The earlier proof relied on the adaptivity of the Turing-reduction to find a Kolmogorov-random string of polynomial length using the set Rₖ as oracle. Our new non-adaptive result relies on a new fundamental fact about the set Rₖ, namely each initial segment of the characteristic sequence of Rₖ is not compressible by recursive means. As a partial converse to our claim we show that strings of high Kolmogorov-complexity when used as advice are not much more useful than randomly chosen strings.