Lu, Zhenjian ;
Oliveira, Igor C. ;
Zimand, Marius
Optimal Coding Theorems in TimeBounded Kolmogorov Complexity
Abstract
The classical coding theorem in Kolmogorov complexity states that if an nbit string x is sampled with probability δ by an algorithm with prefixfree domain then 𝖪(x) ≤ log(1/δ) + O(1). In a recent work, Lu and Oliveira [Zhenjian Lu and Igor C. Oliveira, 2021] established an unconditional timebounded 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 timebounded setting, as it achieves a O(log(1/δ)) bound instead of the informationtheoretic optimal log(1/δ).
Motivated by this discrepancy, we investigate optimal coding theorems in the timebounded 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 polynomialtime 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 nearoptimal parameters.
• Optimal coding theorem for pK^t and unconditional AntunesFortnow. 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 worstcase running times of languages that are in average polynomialtime 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 TimeBounded Kolmogorov Complexity}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {92:192:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772358},
ISSN = {18688969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16433},
URN = {urn:nbn:de:0030drops164331},
doi = {10.4230/LIPIcs.ICALP.2022.92},
annote = {Keywords: computational complexity, randomized algorithms, Kolmogorov complexity}
}
28.06.2022
Keywords: 

computational complexity, randomized algorithms, Kolmogorov complexity 
Seminar: 

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Issue date: 

2022 
Date of publication: 

28.06.2022 