Optimal probabilistic polynomial time compression and the Slepian-Wolf theorem: tighter version and simple proofs

2018/02/02 by Bauwens, Bruno
#68Q30 #94A15 #94A24 #FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.1802.00750

Abstract

We give simplify the proofs of the 2 results in Marius Zimand's paper "Kolmogorov complexity version of Slepian-Wolf coding, proceedings of STOC 2017, p22--32". The first is a universal polynomial time compression algorithm: on input ε > 0, a number k and a string x it computes in polynomial time with probability 1-ε a program that outputs x and has length k + O(log² (|x|/ε)), provided that there exists such a program of length at most k. The second result, is a distributed compression algorithm, in which several parties each send some string to a common receiver. Marius Zimand proved a variant of the Slepian-Wolf theorem using Kolmogorov complexity (in stead of Shannon entropy). With our simpler proof we improve the parameters of Zimand's result.

Related

• Universal almost optimal compression and Slepian-Wolf coding in probabilistic polynomial time
• Kolmogorov complexity version of Slepian-Wolf coding
• Distributed compression through the lens of algorithmic information theory: a primer
• On the Combinatorial Version of the Slepian-Wolf Problem
• Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity