Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2015

Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem

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.
No file

Dates and versions

lirmm-01233012 , version 1 (24-11-2015)

Identifiers

Cite

Daniyar Chumbalov, Andrei Romashchenko. Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem. MFCS: Mathematical Foundations of Computer Science, Aug 2015, Milan, Italy. pp.235-247, ⟨10.1007/978-3-662-48054-0_20⟩. ⟨lirmm-01233012⟩
144 View
0 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More