2015/06/01 by Alexander Kozachinskiy, Kozachinskiy, Alexander
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC
paper · pdf · doi:10.48550/arxiv.1506.00617
arxiv created 2015/09/08 · arxiv updated 2015/09/09
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, which is studied in the classical coding theory, we allow them to interact. They may also use shared randomness. We show, that Alice can transmit X to Bob in expected H(X|Y) + 2√(H(X|Y)) + O(log2((1)/(ε))) number of bits. Moreover, we show that every one-round protocol π with information complexity I can be compressed to the (many-round) protocol with expected communication about I + 2√(I) bits. This improves a result by Braverman and Rao \citebraverman2011information, where they had 5√(I). Further, we show how to solve this problem (transmitting X) using 3H(X|Y) + O(log2((1)/(ε))) bits and 4 rounds on average. This improves a result of~\citebrody2013towards, where they had 4H(X|Y) + O(log1/ε) 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) + Ω(log2((1)/(ε))) bits on average.