Towards bridging the gap between theory and practice for the Slepian-Wolf problem

We address practical coding schemes for the Slepian-Wolf distributed data compression problem. We consider three approaches. First, we apply a source-splitting technique to code at any rate in the achievable rate region with low complexity. It is well known that vertices in the achievable rate region can be implemented with low complexity. The source-splitting approach transforms any achievable rate point into a vertex in a higher-dimensional Slepian-Wolf achievable rate region. Secondly, we consider linear programming relaxations of the maximum-likelihood decoding problem. We give a polynomial complexity construction for linear codes with a certificate property. Lastly, when the decoder does not have any knowledge of the source statistics, we present practical schemes for universal decoding, a topic heretofore confined primarily to theory.