On Slepian-Wolf Theorem with Interaction

摘要

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/ε)) bits on average in 2H(X|Y)/r+2 rounds on average. Setting r = [{the square root of}(H(X|Y))] and using a result of [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{the square root of}I bits. This improves a result by Braverman and Rao [3], where they had I + 5{the square root of}I. Further, we show (by setting r = [H(X|Y)]) how to solve this problem (transmitting X) using 2H(X|Y)+O(log_2(1/ε)) bits and 4 rounds on average. This improves a result of [4], where they had 4H(X|Y) + O(log 1/ε) 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/ε)) bits on average.