The Library
Probabilistic Kolmogorov complexity with applications to average-case complexity
Tools
Goldberg, Halley, Kabanets, Valentine, Lu, Zhenjian and Oliveira, Igor C. (2022) Probabilistic Kolmogorov complexity with applications to average-case complexity. In: Computational Complexity Conference (CCC), Philadelphia, PA, USA, 21–23 Jul 2022. Published in: 37th Computational Complexity Conference (CCC 2022), 234 16:1-16:60. ISBN 9783959772419. doi:10.4230/LIPIcs.CCC.2022.16 ISSN 1868-8969.
|
PDF
WRAP-probabilistic-Kolmogorov-complexity-applications-average-case-complexity-Oliveira-2022.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (1268Kb) | Preview |
|
PDF
WRAP-probabilistic-Kolmogorov-complexity-applications-average-case-complexity-Oliveira-2022.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (985Kb) |
Official URL: https://doi.org/10.4230/LIPIcs.CCC.2022.16
Abstract
Understanding the relationship between the worst-case and average-case complexities of NP and of other subclasses of PH is a long-standing problem in complexity theory. Over the last few years, much progress has been achieved in this front through the investigation of meta-complexity: the complexity of problems that refer to the complexity of the input string x (e.g., given a string x, estimate its time-bounded Kolmogorov complexity). In particular, [Shuichi Hirahara, 2021] employed techniques from meta-complexity to show that if DistNP ⊆ AvgP then UP ⊆ DTIME[2^{O(n/log n)}]. While this and related results [Shuichi Hirahara and Mikito Nanashima, 2021; Lijie Chen et al., 2022] offer exciting progress after a long gap, they do not survive in the setting of randomized computations: roughly speaking, "randomness" is the opposite of "structure", and upper bounding the amount of structure (time-bounded Kolmogorov complexity) of different objects is crucial in recent applications of meta-complexity. This limitation is significant, since randomized computations are ubiquitous in algorithm design and give rise to a more robust theory of average-case complexity [Russell Impagliazzo and Leonid A. Levin, 1990].
In this work, we develop a probabilistic theory of meta-complexity, by incorporating randomness into the notion of complexity of a string x. This is achieved through a new probabilistic variant of time-bounded Kolmogorov complexity that we call pK^t complexity. Informally, pK^t(x) measures the complexity of x when shared randomness is available to all parties involved in a computation. By porting key results from meta-complexity to the probabilistic domain of pK^t complexity and its variants, we are able to establish new connections between worst-case and average-case complexity in the important setting of probabilistic computations:
- If DistNP ⊆ AvgBPP, then UP ⊆ RTIME[2^O(n/log n)].
- If DistΣ^P_2 ⊆ AvgBPP, then AM ⊆ BPTIME[2^O(n/log n)].
- In the fine-grained setting [Lijie Chen et al., 2022], we get UTIME[2^O(√{nlog n})] ⊆ RTIME[2^O(√{nlog n})] and AMTIME[2^O(√{nlog n})] ⊆ BPTIME[2^O(√{nlog n})] from stronger average-case assumptions.
- If DistPH ⊆ AvgBPP, then PH ⊆ BPTIME[2^O(n/log n)]. Specifically, for any
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > Q Science (General) Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Kolmogorov complexity, Computational complexity , Machine learning | ||||||
Journal or Publication Title: | 37th Computational Complexity Conference (CCC 2022) | ||||||
Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | ||||||
ISBN: | 9783959772419 | ||||||
ISSN: | 1868-8969 | ||||||
Official Date: | 11 July 2022 | ||||||
Dates: |
|
||||||
Volume: | 234 | ||||||
Page Range: | 16:1-16:60 | ||||||
DOI: | 10.4230/LIPIcs.CCC.2022.16 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Date of first compliant deposit: | 20 May 2022 | ||||||
Date of first compliant Open Access: | 20 May 2022 | ||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | Computational Complexity Conference (CCC) | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Philadelphia, PA, USA | ||||||
Date(s) of Event: | 21–23 Jul 2022 | ||||||
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