Locally Decodable Slepian-Wolf Compression

This paper investigates the Slepian-Wolf distributed compression of two sources Xn and Yn with the additional property that any pair (Xi, Yi) should reliably be decoded by probing a small number d of compressed bits. We show that for certain source distributions, the error probability of any such local decoder is lower bounded by 2-O(d), in the worst case over index i, whenever one of the sources is compressed below its entropy. Unlike the single-source setup, it is thus impossible to simultaneously achieve constant local decodability d and vanishing local decoding error probability as n increases. We also provide a compression scheme with a local decoder that almost achieves the above lower bound.