Interactive Communication of Balanced Distributions and of Correlated Files
Author:
- Alon OrlitskyAOAlon Orlitsky
- 1 November 1993
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 6 (4) , 548-564
Abstract
$( X,Y )$ is a pair of random variables distributed over a support set S. Person $P_X $ knows X, person $P_Y $ knows Y, and both know S. Using a predetermined protocol, they exchange binary messages for $P_Y $ to learn X. $P_X$ may or may not learn Y. The m-message complexity $\hat C_m $ is the number of information bits that must be transmitted (by both persons) in, the worst case if only m messages are allowed. $\hat C_\infty $ is the number of bits required when there is no restriction on the number of messages exchanged. A natural class of random pairs is considered. $\hat \mu $ is the maximum number of X values possible with a given Y value. $\hat \eta $ is the maximum number of Y values possible with a given X value. The random pair $( X,Y )$ is balanced if $\hat \mu = \hat \eta $. The following hold for all balanced random pairs. One-way communication requires at most twice the minimum number of bits: $\hat C_1 \leqq 2\hat C_\infty + 1$. This bound is almost tight: For every $\alpha $, there is a balanced random pair for which $\hat C_1 \geqq 2\hat C_\infty - 6\geqq \alpha $. Three-message communication is asymptotically optimum, $\hat C_3 \leqq \hat C_\infty + 3\log \hat C_\infty + 11$. More importantly, the number of bits required is only negligibly larger than the number needed when $P_X $ knows Y in advance, $\hat C_\infty \leqq \hat C_3 \leqq \log \hat\mu + 3\log \log \hat \mu + 11$. These results are applied to the following correlated files problem. X and Y are binary strings (files) within a small edit distance from each other. $P_X $ knows X, while $P_Y $ knows Y and wants to learn X. The above results imply efficient three-message protocols for conveying X to $P_Y $. Efficient one-way protocols are provided for certain restricted cases and their possible generalizations are discussed.
Keywords
This publication has 13 references indexed in Scilit:
- Average-case interactive communicationIEEE Transactions on Information Theory, 1992
- Worst-case interactive communication. II. Two messages are not optimalIEEE Transactions on Information Theory, 1991
- Rounds in communication complexity revisited1991
- Worst-case interactive communication. I. Two messages are almost optimalIEEE Transactions on Information Theory, 1990
- Fredman–Komlós bounds and information theorySIAM Journal on Algebraic Discrete Methods, 1986
- Constructing $O(n\log n)$ Size Monotone Formulae for the kth Threshold Function of n Boolean VariablesSIAM Journal on Computing, 1986
- Storing a Sparse Table with 0 (1) Worst Case Access TimeJournal of the ACM, 1984
- On the Size of Separating Systems and Families of Perfect Hash FunctionsSIAM Journal on Algebraic Discrete Methods, 1984
- Lower bounds on information transfer in distributed computations1978
- The zero-error side information problem and chromatic numbers (Corresp.)IEEE Transactions on Information Theory, 1976