Paper Info
Title
Practical Universal Data Exchange using Polar Codes
Abstract
In the multiparty data exchange problem, parties with correlated data seek to recover each-other's data. We study practical, universal schemes for this problem that accomplish data exchange using optimal rate communication for any distribution of observations. Our focus in this work is on binary symmetric distributions where each user observes bit sequences with uniform marginals. We consider binary symmetric Markov trees as a natural multiparty extension of the binary symmetric source and seek universally rate optimal algorithms for this family. Our main theoretical result is a completeness theorem which shows that any universal Slepian-Wolf scheme can be converted efficiently to a universal data exchange scheme for a subfamily of binary symmetric Markov trees. We instantiate this result using Polar codes. In particular, we provide a universal Slepian-Wolf code using Polar codes and use our reduction algorithm to convert it to a multiparty data exchange protocol. The resulting scheme provides the first practical construction of codes for universal data exchange, which we evaluate numerically.
Year
DOI
Venue
2019
10.1109/ITW44776.2019.8989022
2019 IEEE Information Theory Workshop (ITW)
Keywords
Field
DocType
practical universal data exchange,Polar codes,multiparty data exchange problem,correlated data,universal schemes,optimal rate communication,binary symmetric distributions,binary symmetric Markov trees,natural multiparty extension,binary symmetric source,universally rate optimal algorithms,Slepian-Wolf scheme,universal data exchange scheme,Slepian-Wolf code,multiparty data exchange protocol
Discrete mathematics,Data exchange,Gödel's completeness theorem,Computer science,Markov chain,Polar,Binary number
Conference
ISSN
ISBN
Citations 
2475-420X
978-1-5386-6901-3
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Soumya Jyoti Banerjee153.95
Himanshu Tyagi211813.82