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

Bruno Bauwens, Marius Zimand

In a lossless compression system with target lengths, a compressor $\mathcal{C}$ maps an integer $m$ and a binary string $x$ to an $m$-bit code $p$, and if $m$ is sufficiently large,…