A Kolmogorov-Complexity Theoretic Version of the Slepian-Wolf Theorem

Speaker : Marius Zimand


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 (1974) 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 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 talk is to present the main ideas in an accessible way skipping some technical details.