Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

[img]
Preview
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

Request Changes to record.

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:
DateEvent
2019Published
19 April 2019Accepted
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:
Project/Grant IDRIOXX Funder NameFunder ID
615075Seventh Framework Programmehttp://dx.doi.org/10.13039/100011102
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:
  • Other Repository

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us