License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.92
URN: urn:nbn:de:0030-drops-164331
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16433/
 Go to the corresponding LIPIcs Volume Portal

Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity

 pdf-format:

Abstract

The classical coding theorem in Kolmogorov complexity states that if an n-bit string x is sampled with probability δ by an algorithm with prefix-free domain then 𝖪(x) ≤ log(1/δ) + O(1). In a recent work, Lu and Oliveira [Zhenjian Lu and Igor C. Oliveira, 2021] established an unconditional time-bounded version of this result, by showing that if x can be efficiently sampled with probability δ then rKt(x) = O(log(1/δ)) + O(log n), where rKt denotes the randomized analogue of Levin’s Kt complexity. Unfortunately, this result is often insufficient when transferring applications of the classical coding theorem to the time-bounded setting, as it achieves a O(log(1/δ)) bound instead of the information-theoretic optimal log(1/δ).
Motivated by this discrepancy, we investigate optimal coding theorems in the time-bounded setting. Our main contributions can be summarised as follows.
• Efficient coding theorem for rKt with a factor of 2. Addressing a question from [Zhenjian Lu and Igor C. Oliveira, 2021], we show that if x can be efficiently sampled with probability at least δ then rKt(x) ≤ (2 + o(1)) ⋅ log(1/δ) + O(log n). As in previous work, our coding theorem is efficient in the sense that it provides a polynomial-time probabilistic algorithm that, when given x, the code of the sampler, and δ, it outputs, with probability ≥ 0.99, a probabilistic representation of x that certifies this rKt complexity bound.
• Optimality under a cryptographic assumption. Under a hypothesis about the security of cryptographic pseudorandom generators, we show that no efficient coding theorem can achieve a bound of the form rKt(x) ≤ (2 - o(1)) ⋅ log(1/δ) + poly(log n). Under a weaker assumption, we exhibit a gap between efficient coding theorems and existential coding theorems with near-optimal parameters.
• Optimal coding theorem for pK^t and unconditional Antunes-Fortnow. We consider pK^t complexity [Halley Goldberg et al., 2022], a variant of rKt where the randomness is public and the time bound is fixed. We observe the existence of an optimal coding theorem for pK^t, and employ this result to establish an unconditional version of a theorem of Antunes and Fortnow [Luis Filipe Coelho Antunes and Lance Fortnow, 2009] which characterizes the worst-case running times of languages that are in average polynomial-time over all 𝖯-samplable distributions.

BibTeX - Entry

```@InProceedings{lu_et_al:LIPIcs.ICALP.2022.92,
author =	{Lu, Zhenjian and Oliveira, Igor C. and Zimand, Marius},
title =	{{Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity}},
booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages =	{92:1--92:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-235-8},
ISSN =	{1868-8969},
year =	{2022},
volume =	{229},
editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address =	{Dagstuhl, Germany},
URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16433},
URN =		{urn:nbn:de:0030-drops-164331},
doi =		{10.4230/LIPIcs.ICALP.2022.92},
annote =	{Keywords: computational complexity, randomized algorithms, Kolmogorov complexity}
}```

 Keywords: computational complexity, randomized algorithms, Kolmogorov complexity Collection: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) Issue Date: 2022 Date of publication: 28.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy