Kolmogorov complexity version of Slepian-Wolf coding

DOI10.1145/3055399.3055421MaRDI QIDQ4977957zbMATH OpenOpenAlexFDO

Authors Marius Zimand

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.03602

zbMATH Keywords

distributed compressionextractorKolmogorov complexitySlepian-Wolf theorem

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: Alice and Bob are given two correlated n-bit strings x_1 and, respectively, x_2, which they want to losslessly compress and send to Zack. They can either collaborate by sharing their strings, or work separately. We show that there is no disadvantage in the second scenario: Alice and Bob, without knowing the other party's string, can achieve almost optimal compression in the sense of Kolmogorov complexity. Furthermore, compression takes polynomial time and can be made at any combination of lengths that satisfy some necessary conditions (modulo additive polylog terms). More precisely, there exist probabilistic algorithms E_1, E_2, and deterministic algorithm D, with E_1 and E_2 running in polynomial time, having the following behavior: if n_1, n_2 are two integers satisfying n_1 + n_2 geq C(x_1,x_2), n_1 geq C(x_1 | x_2), n_2 geq C(x_2 | x_1), then for i in {1,2}, E_i on input x_i and n_i outputs a string of length n_i + polylog n such that D on input E_1(x_1), E_2(x_2) reconstructs (x_1,x_2) with high probability (where C(x) denotes the plain Kolmogorov complexity of x, and C(x mid y) is the complexity of x conditioned by y). Our main result is more general, as it deals with the compression of any constant number of correlated strings. It is an analog in the framework of algorithmic information theory of the classic Slepian-Wolf Theorem, a fundamental result in network information theory, in which x_1 and x_2 are realizations of two discrete random variables formed by drawing independently n times from a joint distribution. Also, in the classical result, the decompressor needs to know the joint distribution of the sources. In our result no type of independence is assumed and the decompressor does not have any apriori information about the sources that are compressed, and it still is the case that distributed compression is on a par with centralized compression.

Recommendations

• Distributed Compression through the Lens of Algorithmic Information Theory: A Primer
• Randomized polynomial time protocol for combinatorial Slepian-Wolf problem
• On Slepian-Wolf theorem with interaction
• On Slepian-Wolf theorem with interaction
• A proof of the data compression theorem of Slepian and Wolf for ergodic sources (Corresp.)

Cited in

(5)

• Randomized polynomial time protocol for combinatorial Slepian-Wolf problem
• Sequential codes, lossless compression of individual sequences, and Kolmogorov complexity
• An operational characterization of mutual information in algorithmic information theory
• Universal almost optimal compression and Slepian-Wolf coding in probabilistic polynomial time
• Combinatorial version of the Slepian-Wolf coding theorem for binary strings

This page was built for publication: Kolmogorov complexity version of Slepian-Wolf coding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4977957)