. "IEEE Computer Society 2010" . "Derandomizing from random strings"@en . . "RIV/67985840:_____/10:00352483!RIV11-MSM-67985840" . "4"^^ . "6"^^ . . . . "1"^^ . "000286932700007" . . "Buhrman, H." . "Kouck\u00FD, Michal" . . "Fortnow, L." . "Cambridge" . "Kolmogorov random strings; reducibility; complexity classes"@en . "Derandomizing from random strings"@en . . "Derandomizing from random strings" . "2010-06-09+02:00"^^ . "[0937B447BF60]" . "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."@en . . . "Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010" . "Derandomizing from random strings" . "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." . . . . "978-0-7695-4060-3" . "Los Alamitos" . . "P(1M0545), P(GAP202/10/0854), P(IAA100190902), Z(AV0Z10190503)" . "RIV/67985840:_____/10:00352483" . "253411" . . "Loff, B." . . . . . .