Randomized polynomial time protocol for combinatorial Slepian-Wolf problem

DOI10.1007/978-3-662-48054-0_20MaRDI QIDQ2946394zbMATH OpenOpenAlexFDO

Authors Daniyar Chumbalov, Andrei Romashchenko

Publication date 16 September 2015

Published in Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.02899

zbMATH Keywords

coding theorycommunication complexitypseudo-random permutationsrandomized encodingSlepian-Wolf coding

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Communication complexity, information complexity (68Q11) Randomized algorithms (68W20)

Abstract: We study 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 $alphan$. 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. For an asymmetric variant of this problem (where one of the Senders transmits the input string to the Receiver without compression) with deterministic encoding a nontrivial lower bound was found by A.Orlitsky and K.Viswanathany. In our paper we prove a new lower bound for the schemes with syndrome coding, where at least one of the Senders uses linear encoding of the input string. For the combinatorial Slepian-Wolf problem with randomized encoding the theoretical optimum of communication complexity was recently found by the first author, though effective protocols with optimal lengths of messages remained unknown. We close this gap and present a polynomial time randomized protocol that achieves the optimal communication complexity.

Recommendations

• Combinatorial version of the Slepian-Wolf coding theorem for binary strings
• On Slepian-Wolf theorem with interaction
• On Slepian-Wolf theorem with interaction
• Kolmogorov complexity version of Slepian-Wolf coding
• Interactive Communication of Balanced Distributions and of Correlated Files

Cites work

• Combinatorial interpretation of Kolmogorov complexity
• Combinatorial version of the Slepian-Wolf coding theorem for binary strings
• Conditional complexity and codes
• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 5771375 (Why is no real title available?)
• Inequalities for Shannon entropy and Kolmogorov complexity
• Information theory. Coding theorems for discrete memoryless systems
• Interactive Communication of Balanced Distributions and of Correlated Files
• Noiseless coding of correlated information sources
• Scrambling adversarial errors using few random bits, optimal information reconciliation, and better private codes

Cited in

(5)

• Towards a polynomial-time randomized algorithm for closed product-form networks
• Kolmogorov complexity version of Slepian-Wolf coding
• On Slepian-Wolf theorem with interaction
• Branch-and-bound solves random binary IPs in poly(n)-time
• Combinatorial version of the Slepian-Wolf coding theorem for binary strings

This page was built for publication: Randomized polynomial time protocol for combinatorial Slepian-Wolf problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946394)