Abstract
A probabilistic representation of a string x ∈ {0,1}ⁿ is given by the code of a randomized algorithm that outputs x with high probability [Igor C. Oliveira, 2019]. We employ probabilistic representations to establish the first unconditional Coding Theorem in timebounded Kolmogorov complexity. More precisely, we show that if a distribution ensemble 𝒟_m can be uniformly sampled in time T(m) and generates a string x ∈ {0,1}^* with probability at least δ, then x admits a timebounded probabilistic representation of complexity O(log(1/δ) + log (T) + log(m)). Under mild assumptions, a representation of this form can be computed from x and the code of the sampler in time polynomial in n = x.
We derive consequences of this result relevant to the study of data compression, pseudodeterministic algorithms, time hierarchies for sampling distributions, and complexity lower bounds. In particular, we describe an instancebased searchtodecision reduction for Levin’s Kt complexity [Leonid A. Levin, 1984] and its probabilistic analogue rKt [Igor C. Oliveira, 2019]. As a consequence, if a string x admits a succinct timebounded representation, then a nearoptimal representation can be generated from x with high probability in polynomial time. This partially addresses in a timebounded setting a question from [Leonid A. Levin, 1984] on the efficiency of computing an optimal encoding of a string.
BibTeX  Entry
@InProceedings{lu_et_al:LIPIcs.ICALP.2021.94,
author = {Lu, Zhenjian and Oliveira, Igor C.},
title = {{An Efficient Coding Theorem via Probabilistic Representations and Its Applications}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {94:194:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771955},
ISSN = {18688969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14163},
URN = {urn:nbn:de:0030drops141630},
doi = {10.4230/LIPIcs.ICALP.2021.94},
annote = {Keywords: computational complexity, randomized algorithms, Kolmogorov complexity}
}
Keywords: 

computational complexity, randomized algorithms, Kolmogorov complexity 
Collection: 

48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) 
Issue Date: 

2021 
Date of publication: 

02.07.2021 