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

### Speaker : Marius Zimand

### Abstract

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.