The Library
Randomness and intractability in Kolmogorov complexity
Tools
Tools
Tools
Oliveira, Igor C. (2019) Randomness and intractability in Kolmogorov complexity. In: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), Patras, Greece, 9-12 Jul 2019. Published in: Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), 132 32:1-32:14. ISBN 9783959771092. ISSN 1868-8969. doi:10.4230/LIPIcs.ICALP.2019.32
|
PDF
WRAP-randomness-intractability-Kolmogorov-Oliveira-2019.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (524Kb) | Preview |
Official URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2019.32
Abstract
We introduce randomized time-bounded Kolmogorov complexity (rKt), a natural extension of Levin's notion [Leonid A. Levin, 1984] of Kolmogorov complexity. A string w of low rKt complexity can be decompressed from a short representation via a time-bounded algorithm that outputs w with high probability. This complexity measure gives rise to a decision problem over strings: MrKtP (The Minimum rKt Problem). We explore ideas from pseudorandomness to prove that MrKtP and its variants cannot be solved in randomized quasi-polynomial time. This exhibits a natural string compression problem that is provably intractable, even for randomized computations. Our techniques also imply that there is no n^{1 - epsilon}-approximate algorithm for MrKtP running in randomized quasi-polynomial time. Complementing this lower bound, we observe connections between rKt, the power of randomness in computing, and circuit complexity. In particular, we present the first hardness magnification theorem for a natural problem that is unconditionally hard against a strong model of computation.
| Item Type: | Conference Item (Paper) | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
| Divisions: | Faculty of Science > Computer Science | ||||||
| Library of Congress Subject Headings (LCSH): | Computational complexity, Kolmogorov complexity, Cryptography | ||||||
| Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||
| Journal or Publication Title: | Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP) | ||||||
| Publisher: | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik | ||||||
| ISBN: | 9783959771092 | ||||||
| ISSN: | 1868-8969 | ||||||
| Official Date: | 2019 | ||||||
| Dates: |
|
||||||
| Date of first compliant deposit: | 11 November 2019 | ||||||
| Volume: | 132 | ||||||
| Page Range: | 32:1-32:14 | ||||||
| DOI: | 10.4230/LIPIcs.ICALP.2019.32 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Access rights to Published version: | Open Access | ||||||
| RIOXX Funder/Project Grant: |
|
||||||
| Conference Paper Type: | Paper | ||||||
| Title of Event: | 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) | ||||||
| Type of Event: | Conference | ||||||
| Location of Event: | Patras, Greece | ||||||
| Date(s) of Event: | 9-12 Jul 2019 | ||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
