Number of the records: 1
Derandomizing from random strings
- 1.
SYSNO ASEP 0352483 Document Type C - Proceedings Paper (int. conf.) R&D Document Type Conference Paper Title Derandomizing from random strings Author(s) Buhrman, H. (NL)
Fortnow, L. (US)
Koucký, Michal (MU-W) RID, SAI, ORCID
Loff, B. (PT)Source Title Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010. - Los Alamitos : IEEE Computer Society 2010, 2010 - ISBN 978-0-7695-4060-3 Pages s. 58-63 Number of pages 6 s. Action 25th Annual IEEE Conference on Computational Complexity, CCC 2010 Event date 09.06.2010-12.06.2010 VEvent location Cambridge Country US - United States Event type WRD Language eng - English Country US - United States Keywords Kolmogorov random strings ; reducibility ; complexity classes Subject RIV BA - General Mathematics R&D Projects GAP202/10/0854 GA ČR - Czech Science Foundation (CSF) IAA100190902 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR) 1M0545 GA MŠMT - Ministry of Education, Youth and Sports (MEYS) CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000286932700007 EID SCOPUS 77955259331 DOI 10.1109/CCC.2010.15 Annotation 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. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2011
Number of the records: 1