- Derandomizing from random strings
- 25th Annual IEEE Conference on Computational Complexity (CCC 2010), Cambridge, MA, USA
- Book/source title
- 25th Annual IEEE Conference on Computational Complexity
- Book/source subtitle
- proceedings : CCC 2010 : 9-11 June, 2010, Cambridge, Massachusetts, USA
- Pages (from-to)
- Los Alamitos, Calif.: IEEE Computer Society
- ISBN (electronic)
- Document type
- Conference contribution
- Interfacultary Research Institutes
- Institute for Logic, Language and Computation (ILLC)
In this paper we show that BPP is truth-table reducible to the set of Kolmogorov random strings R(K). It was previously known that PSPACE, and hence BPP is Turing-reducible to R(K). The earlier proof relied on the adaptivity of the Turing-reduction to find a Kolmogorov-random string of polynomial length using the set R(K) as oracle. Our new non-adaptive result relies on a new fundamental fact about the set R(K), namely each initial segment of the characteristic sequence of R(K) has high Kolmogorov complexity. As a partial converse to our claim we show that strings of very high Kolmogorov-complexity when used as advice are not much more useful than randomly chosen strings.
- go to publisher's site
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.