Combinatorial Version of the Slepian–Wolf Coding Theorem for Binary Strings

In this paper we study a combinatorial analogue of the Slepian–Wolf coding. We consider communication protocols with three parties (Alice, Bob, and Charlie). Alice and Bob hold binary strings $X$ and $Y$ respectively, of the same length $n$, with the Hamming distance between $X$ and $Y$ bounded by some threshold $c$. Alice and Bob send some messages to Charlie, and then Charlie should reconstruct both $X$ and $Y$. The aim is to optimize communication complexity of a protocol, i.e., to minimize the lengths of messages sent by Alice and Bob.
We show that simple and most natural lower bounds for this problem give in fact the right answer – these bounds can be achieved by some (nontrivial) communication protocols. We consider two principal settings: (i) the Hamming distance between $X$ and $Y$ is an absolute constant $c$, and (ii) the Hamming distance between these strings is $\alpha n$ for some constant fraction $\alpha$. In the first setting we propose a very simple lower bound and a deterministic, polynomial-time for all three participants communication protocol that asymptotically achieves this bound. This protocol is based on the checksums obtained from syndromes of the BCH codes. In the second setting we prove a nontrivial lower bounds for deterministic protocols. But the lower bounds for probabilistic protocols remain very simple, and we construct a protocol that asympotically achieves these simple lower bounds. In this probabilistic protocol we combine the technique of syndromes of linear codes with list-decoding and random hash-functions.