Universal almost optimal compression and Slepian-Wolf coding in probabilistic polynomial time

Journal of the ACM. 2023. Vol. 70. No. 2. Article 9.

Bauwens B. F., Zimand M.

In a lossless compression system with target lengths, a compressor 𝒞 maps an integer m and a binary string x to an m-bit code p, and if m is sufficiently large, a decompressor 𝒟 reconstructs x from p. We call a pair (m,x) achievable for (𝒞,𝒟) if this reconstruction is successful. We introduce the notion of an optimal compressor 𝒞opt by the following universality property: For any compressor-decompressor pair (𝒞,𝒟), there exists a decompressor 𝒟′ such that if (m,x) is achievable for (𝒞,𝒟), then (m + Δ , x) is achievable for (𝒞opt, 𝒟′), where Δ is some small value called the overhead. We show that there exists an optimal compressor that has only polylogarithmic overhead and works in probabilistic polynomial time. Differently said, for any pair (𝒞,𝒟), no matter how slow 𝒞 is, or even if 𝒞 is non-computable, 𝒞opt is a fixed compressor that in polynomial time produces codes almost as short as those of 𝒞. The cost is that the corresponding decompressor is slower.

We also show that each such optimal compressor can be used for distributed compression, in which case it can achieve optimal compression rates as given in the Slepian–Wolf theorem and even for the Kolmogorov complexity variant of this theorem.

Keywords: Kolmogorov complexity, compression algorithms, conductor graph, distributed compression, Slepian-Wolf theorem

Publication based on the results of: Вопросы сложности в теоретической информатике (2020)