
arXiv: 1706.08468
Distributed compression is the task of compressing correlated data by several parties, each one possessing one piece of data and acting separately. The classical Slepian-Wolf theorem (D. Slepian, J. K. Wolf, IEEE Transactions on Inf. Theory, 1973) shows that if data is generated by independent draws from a joint distribution, that is by a memoryless stochastic process, then distributed compression can achieve the same compression rates as centralized compression when the parties act together. Recently, the author (M. Zimand, STOC 2017) has obtained an analogue version of the Slepian-Wolf theorem in the framework of Algorithmic Information Theory (also known as Kolmogorov complexity). The advantage over the classical theorem, is that the AIT version works for individual strings, without any assumption regarding the generative process. The only requirement is that the parties know the complexity profile of the input strings, which is a simple quantitative measure of the data correlation. The goal of this paper is to present in an accessible form that omits some technical details the main ideas from the reference (M. Zimand, STOC 2017).
FOS: Computer and information sciences, Computer Science - Computational Complexity, Computer Science - Information Theory, Information Theory (cs.IT), Computational Complexity (cs.CC)
FOS: Computer and information sciences, Computer Science - Computational Complexity, Computer Science - Information Theory, Information Theory (cs.IT), Computational Complexity (cs.CC)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
