Interactive communication for data exchange

Himanshu Tyagi, Pramod Viswanath, Shun Watanabe

Research output: Contribution to journalArticle

Abstract

Two parties observing correlated data seek to exchange their data using interactive communication. How many bits must they communicate? We propose a new interactive protocol for data exchange, which increases the communication size in steps until the task is done. We also derive a lower bound on the minimum number of bits that is based on relating the data exchange problem to the secret key agreement problem. Our single-shot analysis applies to all discrete random variables and yields upper and lower bounds of a similar form. In fact, the bounds are asymptotically tight and lead to a characterization of the optimal rate of communication needed for data exchange for a general source sequence, such as a mixture of independent and identically distributed (IID) random variables as well as the optimal second-order asymptotic term in the length of communication needed for data exchange for IID random variables, when the probability of error is fixed. This gives a precise characterization of the asymptotic reduction in the length of optimal communication due to interaction; in particular, two-sided Slepian-Wolf compression is strictly suboptimal.

Original languageEnglish (US)
Pages (from-to)26-37
Number of pages12
JournalIEEE Transactions on Information Theory
Volume64
Issue number1
DOIs
StatePublished - Jan 1 2018

Keywords

  • Data exchange
  • Interactive communication
  • Omniscience
  • Secret key agreement

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint Dive into the research topics of 'Interactive communication for data exchange'. Together they form a unique fingerprint.

  • Cite this