On Slepian-Wolf Theorem with Interaction

摘要

Abstract In this paper we study interactive “one-shot” analogues of the classical Slepian–Wolf theorem. Alice receives a value of a random variable X , Bob receives a value of another random variable Y that is jointly distributed with X . Alice’s goal is to transmit X to Bob (with some error probability ε ). Instead of one-way transmission we allow them to interact. They may also use shared randomness. We show, that for every natural r Alice can transmit X to Bob using 1 + 1 r H ( X | Y ) + r + O ( log 2 1 ε ) $left (1 + frac {1}{r}right )H(X|Y) + r + O(log _{2}left (frac {1}{varepsilon }right ))$ bits on average in 2 H ( X | Y ) r + 2 $frac {2H(X|Y)}{r} + 2$ rounds on average. Setting r = ⌈ H ( X | Y ) ⌉ $r = lceil sqrt {H(X|Y)}rceil $ and using a result of Braverman and Garg (2) we conclude that every one-round protocol π with information complexity I can be compressed to a (many-round) protocol with expected communication about I + 2 I $I + 2sqrt {I}$ bits. This improves a result by Braverman and Rao (3), where they had I + 5 I $I+5sqrt {I}$ . Further, we show (by setting r = ⌈ H ( X | Y )⌉) how to solve this problem (transmitting X ) using 2 H ( X | Y ) + O ( log 2 1 ε ) $2H(X|Y) + O(log _{2}left (frac {1}{varepsilon }right ))$ bits and 4 rounds on average. This improves a result of Brody et al. (4), where they had 4 H ( X | Y ) + O ( log 1 / ε ) $4H(X|Y) + O(log 1/varepsilon )$ bits and 10 rounds on average. In the end of the paper we discuss how many bits Alice and Bob may need to communicate on average besides H ( X | Y ). The main question is whether the upper bounds mentioned above are tight. We provide an example of ( X , Y ), such that transmission of X from Alice to Bob with error probability ε requires H ( X | Y ) + Ω log 2 1 ε $H(X|Y) + {Omega }left (log _{2}left (frac {1}{varepsilon }right )right )$ bits on average.