Počet záznamů: 1

Derandomizing from random strings

  1. 1.
    0352483 - MU-W 2011 RIV US eng C - Konferenční příspěvek (zahraniční konf.)
    Buhrman, H. - Fortnow, L. - Koucký, Michal - Loff, B.
    Derandomizing from random strings.
    Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010. Los Alamitos: IEEE Computer Society 2010, 2010, s. 58-63. ISBN 978-0-7695-4060-3.
    [25th Annual IEEE Conference on Computational Complexity, CCC 2010. Cambridge (US), 09.06.2010-12.06.2010]
    Grant CEP: GA ČR GAP202/10/0854; GA AV ČR IAA100190902; GA MŠk(CZ) 1M0545
    Výzkumný záměr: CEZ:AV0Z10190503
    Klíčová slova: Kolmogorov random strings * reducibility * complexity classes
    Kód oboru RIV: BA - Obecná matematika
    http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5497897

    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.
    Trvalý link: http://hdl.handle.net/11104/0191982
    Název souboruStaženoVelikostKomentářVerzePřístup
    Koucky1.pdf1337.3 KBVydavatelský postprintvyžádat