Say Alice and Bob have n-bit strings which are identical except that Bob's contains t "erasures": the corresponding bit may be either zero or one. Alice will send Bob a message he can use to fill in his erased bits. The Slepian-Wolf bound suggests Alice may send as few as t bits, even when Alice does not know which t bits of are erased. We present several protocols acheiving this bound with varying degrees of success. A binary, linear, and deterministic protocol exists only for t ϵ {0, 1, n-1, n}. A nonbinary protocol exists for any t ≤ n ≤ 2m-1, but requires that erasures occur in m-bit blocks. A nonlinear protocol seems promising, but the theory to prove it in general is difficult to explore. Finally, a probabilistic protocol has no parameter constraints, but has suboptimal communication complexity based on an additional parameter c, and will fail with an error-rate Є dependent on c and t.
Say Alice and Bob have n-bit strings which are identical except that Bob's contains t "erasures": the corresponding bit may be either zero or one. Alice will send Bob a message he can use to fill in his erased bits. The Slepian-Wolf bound suggests Alice may send as few as t bits, even when Alice does not know which t bits of are erased. We present several protocols acheiving this bound with varying degrees of success. A binary, linear, and deterministic protocol exists only for t ϵ {0, 1, n-1, n}. A nonbinary protocol exists for any t ≤ n ≤ 2m-1, but requires that erasures occur in m-bit blocks. A nonlinear protocol seems promising, but the theory to prove it in general is difficult to explore. Finally, a probabilistic protocol has no parameter constraints, but has suboptimal communication complexity based on an additional parameter c, and will fail with an error-rate Є dependent on c and t.
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)+2H(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+2I bits. This improves a result by Braverman and Rao \cite{braverman2011information}, where they had 5I. 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~\cite{brody2013towards}, 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.
Suppose Alice holds a uniformly random string X ∈ {0, 1}N and Bob holds a noisy version Y of X where each bit of X is flipped independently with probability e ∈ [0, 1/2]. Alice and Bob would like to extract a common random string of min-entropy at least k. In this work, we establish the communication versus success probability trade-off for this problem by giving a protocol and a matching lower bound (under the restriction that the string to be agreed upon is determined by Alice's input X). Specifically, we prove that in order for Alice and Bob to agree on a common string with probability 2-γk (γk ≥ 1), the optimal communication (up to o(k) terms, and achievable for large N) is precisely [EQUATION], where C:= 4e(1 - e). In particular, the optimal communication to achieve Ω(1) agreement probability approaches 4e(1 - e)k.
We also consider the case when Y is the output of the binary erasure channel on X, where each bit of Y equals the corresponding bit of X with probability 1 - e and is otherwise erased (that is, replaced by a '?'). In this case, the communication required becomes [EQUATION]. In particular, the optimal communication to achieve Ω(1) agreement probability approaches ek, and with no communication the optimal agreement probability approaches [EQUATION].
Our protocols are based on covering codes and extend the approach of (Bogdanov and Mossel, 2011) for the zero-communication case. Our lower bounds rely on hypercontractive inequalities. For the model of bit-flips, our argument extends the approach of (Bogdanov and Mossel, 2011) by allowing communication; for the erasure model, to the best of our knowledge the needed hypercontractivity statement was not studied before, and it was established (given our application) by (Nair and Wang 2015). We also obtain information complexity lower bounds for these tasks, and together with our protocol, they shed light on the recently popular most informative Boolean function conjecture of Courtade and Kumar.
Suppose Alice holds a uniformly random string X in {0,1}^N and Bob holds a noisy version Y of X where each bit of X is flipped independently with probability epsilon in [0,1/2]. Alice and Bob would like to extract a common random string of min-entropy at least k. In this work, we establish the communication versus success probability trade-off for this problem by giving a protocol and a matching lower bound (under the restriction that the string to be agreed upon is determined by Alice's input X). Specifically, we prove that in order for Alice and Bob to agree on a common string with probability 2^{-gamma k} (gamma k >= 1), the optimal communication (up to o(k) terms, and achievable for large N) is precisely (C *(1-gamma) - 2 * sqrt{ C * (1-C) gamma}) * k, where C := 4 * epsilon * (1-epsilon). In particular, the optimal communication to achieve Omega(1) agreement probability approaches 4 * epsilon * (1-epsilon) * k. We also consider the case when Y is the output of the binary erasure channel on X, where each bit of Y equals the corresponding bit of X with probability 1-epsilon and is otherwise erased (that is, replaced by a "?"). In this case, the communication required becomes (epsilon * (1-gamma) - 2 * sqrt{ epsilon * (1-epsilon) * gamma}) * k. In particular, the optimal communication to achieve Omega(1) agreement probability approaches epsilon * k, and with no communication the optimal agreement probability approaches 2^{- (1-sqrt{1-epsilon})/(1+sqrt{1-epsilon}) * k}. Our protocols are based on covering codes and extend the approach of (Bogdanov and Mossel, 2011) for the zero-communication case. Our lower bounds rely on hypercontractive inequalities. For the model of bit-flips, our argument extends the approach of (Bogdanov and Mossel, 2011) by allowing communication; for the erasure model, to the best of our knowledge the needed hypercontractivity statement was not studied before, and it was established (given our application) by (Nair and Wang 2015). We also obtain information complexity lower bounds for these tasks, and together with our protocol, they shed light on the recently popular "most informative Boolean function" conjecture of Courtade and Kumar.
Alice and Bob are connected via a two-way channel, and Alice wants to send a message of L bits to Bob. An adversary flips an arbitrary but finite number of bits, T, on the channel. This adversary knows our algorithm and Alice's message, but does not know any private random bits generated by Alice or Bob, nor the bits sent over the channel, except when these bits can be predicted by knowledge of Alice's message or our algorithm. We want Bob to receive Alice's message and for both players to terminate, with error probability at most δ > 0, where δ is a parameter known to both Alice and Bob. Unfortunately, the value T is unknown in advance to either Alice or Bob, and the value L is unknown in advance to Bob.
Alice and Bob want to know if two strings of length n are almost equal. That is, do the strings differ on at most a bits? Let 0 ⩽ a ⩽ n − 1. We show (1) any deterministic protocol—as well as any error-free quantum protocol ( C * version)—for this problem requires at least n − 2 bits of communication, and (2) a lower bound of n /2 − 1 for error-free Q * quantum protocols. We also show the same results for determining if two strings differ in exactly a bits. Our results are obtained by lower-bounding the ranks of the appropriate matrices.
Alice and Bob want to know if two strings of length n are almost equal. That is, do theydiffer on at most a bits? Let 0 < = a < = n- 1. We show that any deterministic protocol, as wellas any error-free quantum protocol ( C * version), for this problem requires at least n- 2 bits ofcommunication. We show the same bounds for the problem of determining if two strings differ in exactly a bits. We also prove a lower bound of n/2- 1 for error-free Q * quantum protocols.Our results are obtained by lower-bounding the ranks of the appropriate matrices.