### 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 language | English (US) |
---|---|

Pages (from-to) | 26-37 |

Number of pages | 12 |

Journal | IEEE Transactions on Information Theory |

Volume | 64 |

Issue number | 1 |

DOIs | |

State | Published - Jan 1 2018 |

### Fingerprint

### Keywords

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

### ASJC Scopus subject areas

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

### Cite this

*IEEE Transactions on Information Theory*,

*64*(1), 26-37. https://doi.org/10.1109/TIT.2017.2769124

**Interactive communication for data exchange.** / Tyagi, Himanshu; Viswanath, Pramod; Watanabe, Shun.

Research output: Contribution to journal › Article

*IEEE Transactions on Information Theory*, vol. 64, no. 1, pp. 26-37. https://doi.org/10.1109/TIT.2017.2769124

}

TY - JOUR

T1 - Interactive communication for data exchange

AU - Tyagi, Himanshu

AU - Viswanath, Pramod

AU - Watanabe, Shun

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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.

AB - 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.

KW - Data exchange

KW - Interactive communication

KW - Omniscience

KW - Secret key agreement

UR - http://www.scopus.com/inward/record.url?scp=85032732128&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85032732128&partnerID=8YFLogxK

U2 - 10.1109/TIT.2017.2769124

DO - 10.1109/TIT.2017.2769124

M3 - Article

AN - SCOPUS:85032732128

VL - 64

SP - 26

EP - 37

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 1

ER -