Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem

Chumbalov Daniyar 1 Andrei Romashchenko 2
1 EPFL - Ecole Polytechnique Fédérale de Lausanne
2 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We consider the following combinatorial version of the Slepian–Wolf coding scheme. Two isolated Senders are given binary strings X and Y respectively; the length of each string is equal to n, and the Hamming distance between the strings is at most αn. The Senders compress their strings and communicate the results to the Receiver. Then the Receiver must reconstruct both strings X and Y. The aim is to minimise the lengths of the transmitted messages. The theoretical optimum of communication complexity for this scheme (with randomised parties) was found in [6], though effective protocols with optimal lengths of messages remained unknown. We close this gap and present for this communication problem a polynomial time randomised protocol that achieves the optimal communication complexity.
Keywords : Slepian-Wolf coding Communication complexity Coding theory Randomized encoding Pseudo-random permutations
Type de document :
Communication dans un congrès
MFCS: Mathematical Foundations of Computer Science, Aug 2015, Milan, Italy. LNCS (9235), pp.235-247, 2015, 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II. 〈10.1007/978-3-662-48054-0_20〉
Liste complète des métadonnées
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01233012
Contributeur : Andrei Romashchenko <>
Soumis le : mardi 24 novembre 2015 - 12:11:35
Dernière modification le : jeudi 11 janvier 2018 - 06:27:05

Identifiants

Collections

INSMI | ESCAPE | LIRMM | MIPS | TDS-MACS | UNIV-MONTPELLIER

Citation

Chumbalov Daniyar, Andrei Romashchenko. Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem. MFCS: Mathematical Foundations of Computer Science, Aug 2015, Milan, Italy. LNCS (9235), pp.235-247, 2015, 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II. 〈10.1007/978-3-662-48054-0_20〉. 〈lirmm-01233012〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

76

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD