Geodesic
Combinatorial Version of the Slepian–Wolf Coding Theorem for Binary Strings
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 10 (2013), pp. 656-665 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: Distributed source coding, Slepian–Wolf theorem, communication complexity. 
@article{SEMR_2013_10_a38,
     author = {D. A. Chumbalov},
     title = {Combinatorial {Version} of the {Slepian{\textendash}Wolf} {Coding} {Theorem} for {Binary} {Strings}},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {656--665},
     year = {2013},
     volume = {10},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2013_10_a38/}
}
TY  - JOUR
AU  - D. A. Chumbalov
TI  - Combinatorial Version of the Slepian–Wolf Coding Theorem for Binary Strings
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2013
SP  - 656
EP  - 665
VL  - 10
UR  - http://geodesic.mathdoc.fr/item/SEMR_2013_10_a38/
LA  - en
ID  - SEMR_2013_10_a38
ER  - 
%0 Journal Article
%A D. A. Chumbalov
%T Combinatorial Version of the Slepian–Wolf Coding Theorem for Binary Strings
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2013
%P 656-665
%V 10
%U http://geodesic.mathdoc.fr/item/SEMR_2013_10_a38/
%G en
%F SEMR_2013_10_a38
D. A. Chumbalov. Combinatorial Version of the Slepian–Wolf Coding Theorem for Binary Strings. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 10 (2013), pp. 656-665. http://geodesic.mathdoc.fr/item/SEMR_2013_10_a38/

[1] D. Slepian, J. K. Wolf, “Noiseless Coding of Correlated Information Sources”, IEEE Transactions on Information Theory, 19 (1973), 471–480 | MR | Zbl

[2] A. Orlitsky, K. Viswanathan, “One-Way Communication and Error-Correcting Codes”, IEEE Transactions on Information Theory, 49:7 (2003), 1781–1788 | MR

[3] A. Chuklin, Effective protocols for low-distance file synchronization, 2011, arXiv: (in Russian) 1102.4712

[4] N. Gehrig, P. L. Dragotti, “Symmetric and asymmetric Slepian–Wolf codes with systematic and nonsystematic linear codes”, IEEE Communications Letters, 9:1 (2005), 61–63

[5] P. Tan, J. Li, “A practical and optimal symmetric Slepian–Wolf compression strategy using syndrome formers and inverse syndrome formers”, Proceeding of the 43rd Annual Allerton Conference on Communication, Control and Computing (2005)

[6] V. Guruswami, J. Hastad, M. Sudan, D. Zuckerman, “Combinatorial bounds for list decoding”, IEEE Transactions on Information Theory, 48:5 (2002), 1021–1035 | MR

[7] F. J. MacWilliams, N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977 | MR | MR | Zbl