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 e). 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 \(\left (1 + \frac {1}{r}\right )H(X|Y) + r + O(\log _{2}\left (\frac {1}{\varepsilon }\right ))\) bits on average in \(\frac {2H(X|Y)}{r} + 2\) rounds on average. Setting \(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\sqrt {I}\) bits. This improves a result by Braverman and Rao (3), where they had \(I+5\sqrt {I}\). Further, we show (by setting r = ⌈H(X|Y)⌉) how to solve this problem (transmitting X) using \(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 \(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 e requires \(H(X|Y) + {\Omega }\left (\log _{2}\left (\frac {1}{\varepsilon }\right )\right )\) bits on average.
['Alexander Kozachinskiy']
On Slepian–Wolf Theorem with Interaction