LetXandYbe finite nonempty sets and(X,Y) a pair of random variables taking values inX?Y. We consider communication protocols between two parties,AliceandBob, for generatingXandY.Aliceis provided anx?Xgenerated according to the distribution ofX, and is required to send a message toBobin order to enable him to generatey?Y, whose distribution is the same as that ofY|X=x. Both parties have access to a shared random string generated in advance. LetT[X:Y] be the minimum (over all protocols) of the expected number of bitsAliceneeds to transmit to achieve this. We show that I[X:Y] ? T[X:Y] ? I [X:Y] + 2 log2(I[X:Y]+ O(1). We also consider the worst case communication required for this problem, where we seek to minimize the average number of bitsAlicemust transmit for the worst casex?X. We show that the communication required in this case is related to the capacityC(E) of the channelE, derived from(X,Y) , that mapsx?Xto the distribution ofY|X=x. We also show that the required communicationT(E) satisfiesC(E) ?T(E) ?C(E) + 2 log2(C(E)+1) +O(1). Using the first result, we derive a direct-sum theorem in communication complexity that substantially improves the previous such result shown by Jain, Radhakrishnan, and Sen [In Proc. 30th International Colloquium of Automata, Languages and Programming (ICALP), ser. Lecture Notes in Computer Science, vol. 2719. 2003, pp. 300-315]. These results are obtained by employing a rejection sampling procedure that relates the relative entropy between two distributions to the communication complexity of generating one distribution from the other.
LetXandYbe finite nonempty sets and(X,Y) a pair of random variables taking values inX?Y. We consider communication protocols between two parties,AliceandBob, for generatingXandY.Aliceis provided anx?Xgenerated according to the distribution ofX, and is required to send a message toBobin order to enable him to generatey?Y, whose distribution is the same as that ofY|X=x. Both parties have access to a shared random string generated in advance. LetT[X:Y] be the minimum (over all protocols) of the expected number of bitsAliceneeds to transmit to achieve this. We show that I[X:Y] ? T[X:Y] ? I [X:Y] + 2 log2(I[X:Y]+ O(1). We also consider the worst case communication required for this problem, where we seek to minimize the average number of bitsAlicemust transmit for the worst casex?X. We show that the communication required in this case is related to the capacityC(E) of the channelE, derived from(X,Y) , that mapsx?Xto the distribution ofY|X=x. We also show that the required communicationT(E) satisfiesC(E) ?T(E) ?C(E) + 2 log2(C(E)+1) +O(1). Using the first result, we derive a direct-sum theorem in communication complexity that substantially improves the previous such result shown by Jain, Radhakrishnan, and Sen [In Proc. 30th International Colloquium of Automata, Languages and Programming (ICALP), ser. Lecture Notes in Computer Science, vol. 2719. 2003, pp. 300-315]. These results are obtained by employing a rejection sampling procedure that relates the relative entropy between two distributions to the communication complexity of generating one distribution from the other.
In this paper, we present the following quantum compression protocol `P': Let ρ,σ be quantum states, such that S (ρ∥σ)def= Tr(ρ log ρ - ρ log σ), the relative entropy between ρ and σ, is finite. Alice gets to know the eigendecomposition of ρ. Bob gets to know the eigendecomposition of σ. Both Alice and Bob know S(ρ∥σ) and an error parameter ε. Alice and Bob use shared entanglement and after communication of O((S(ρ∥σ) + 1)/ε4) bits from Alice to Bob, Bob ends up with a quantum state ̃ρ̃, such that F(ρ, ρ̃) ≥ 1-5ε, where F(·) represents fidelity. This result can be considered as a non-commutative generalization of a result due to Braverman and Rao where they considered the special case when ρ and σ are classical probability distributions (or commute with each other) and use shared randomness instead of shared entanglement. We use? to obtain an alternate proof of a direct-sum result for entanglement assisted quantum one-way communication complexity for all relations, which was first shown by Jain et al.. We also present a variant of protocol? in which Bob has some side information about the state with Alice. We show that in such a case, the amount of communication can be further reduced, based on the side information that Bob has. Our second result provides a quantum analog of the widely used classical correlated-sampling protocol. For example, Holenstein used the classical correlated-sampling protocol in his proof of a parallel-repetition theorem for two-player one-round games.
It is known that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings x and y is equal to the length of the longest shared secret key that two parties can establish via a probabilistic protocol with interaction on a public channel, assuming that the parties hold as their inputs x and y , respectively. We determine the worst-case communication complexity of this problem for the setting where the parties can use private sources of random bits. We show that for some x , y the communication complexity of the secret key agreement does not decrease even if the parties have to agree on a secret key, the size of which is much smaller than the mutual information between x and y . However, we discuss a natural class of x , y such that the communication complexity of the protocol declines gradually with the size of the derived secret key. The proof of the main result uses the spectral properties of appropriate graphs and the expander mixing lemma, as well as information-theoretic techniques, including constraint information inequalities and Muchnik’s conditional descriptions. A preliminary version of this article was published in the proceedings of MFCS 2020. In the present version, we give full proofs of all theorems and get rid of the assumption that the number of random bits used in the communication protocols is polynomial.
Let x, y, z be finite sets, X,Y random variables uniformly distributed over x×y, f a function from x×y to Z and 0≤ε&le1. A person PX knows X and a person PY knows Y and they want to exchange X and Y. An eavesdropper who knows their protocol listens to their communication in order to obtain information about f(X, Y). PX and PY want to ensure that for every value (x,y) of (X,Y) the eavesdropper's a priori and a posteriori probabilities of {f(X,Y)=j} are ε-close for all j. Therefore, they encrypt some of the transmitted bits. The problem is to find a protocol that minimizes the number of bits encrypted in the worst case. Two kinds of protocols are considered: deterministic and randomized.
In this paper, we show a direct product theorm in the model of two-party bounded-round public-coin randomized communication complexity. For a relation f subset of X times Y times Z (X,Y,Z are finite sets), let R^{(t), pub}_e (f) denote the two-party t-message public-coin communication complexity of f with worst case error e. We show that for any relation f and positive integer k: R^{(t), pub}_{1 - 2^{-Omega(k/t^2)}}(f^k) = Omega(k/t (R^{(t), pub}_{1/3}(f) - O(t^2))) . In particular, it implies a strong direct product theorem for the two-party constant-message public-coin randomized communication complexity of all relations f. Our result for example implies a strong direct product theorem for the pointer chasing problem. This problem has been well studied for understanding round v/s communication trade-offs in both classical and quantum communication protocols. We show our result using information theoretic arguments. Our arguments and techniques build on the ones used in [Jain 2011], where a strong direct product theorem for the two-party one-way public-coin communication complexity of all relations is shown (that is the special case of our result when t=1). One key tool used in our work and also in [Jain 2011] is a message compression technique due to [Braverman and Rao 2011], who used it to show a direct sum theorem for the two-party bounded-round public-coin randomized communication complexity of all relations. Another important tool that we use is a correlated sampling protocol, which for example, has been used in [Holenstein 2007] for proving a parallel repetition theorem for two-prover games.
In this work we study the problems of common randomness generation (CRG) and secret key generation (SKG). In the CRG problem, two parties, Alice and Bob, receive samples X and Y, respectively, from some joint source distribution μ. The two parties wish to agree on a key consisting of many bits of randomness, by exchanging messages that depend on each party’s respective input and the previous messages. The SKG problem is the same as CRG, except that an eavesdropper who observes the messages must not be able to determine much information about the key. We study the tradeoff between the minimum total length of all messages for a protocol generating a given number of bits of randomness and the minimum possible number of rounds in such a protocol. We construct a source distribution parametrized by positive integers r, n, and l, achieving such a tradeoff in a strong sense: when Alice and Bob can use r + 2 rounds of communication and l ≥ n, they can agree on l bits of entropy by communicating only O(log n) bits, but when they are restricted to r rounds of communication, they require communication of Ω(n^(1/2) / poly log(n)) bits to agree on l bits of entropy. We also prove an analogous result for the setting in which Alice and Bob can amortize, meaning that they receive N i.i.d. samples of (X, Y) from μ, and the communication and key length, respectively, are measured by the ratio of the actual number of bits communicated and the actual key length, respectively, to N.
We study common randomness where two parties have access to i.i.d. samples from a known random source, and wish to generate a shared random key using limited (or no) communication with the largest possible probability of agreement. This problem is at the core of secret key generation in cryptography, with connections to communication under uncertainty and locality sensitive hashing. We take the approach of treating correlated sources as a critical resource, and ask whether common randomness can be generated resource-efficiently. We consider two notable sources in this setup arising from correlated bits and correlated Gaussians. We design the first explicit schemes that use only a polynomial number of samples (in the key length) so that the players can generate shared keys that agree with constant probability using optimal communication. The best previously known schemes were both non-constructive and used an exponential number of samples. In the amortized setting, we characterize the largest achievable ratio of key length to communication in terms of the external and internal information costs, two well-studied quantities in theoretical computer science. In the relaxed setting where the two parties merely wish to improve the correlation between the generated keys of length k, we show that there are no interactive protocols using o(k) bits of communication having agreement probability even as small as 2–o(k). For the related communication problem where the players wish to compute a joint function f of their inputs using i.i.d samples from a known source, we give a simultaneous message passing protocol using 2O(c) bits where c is the interactive randomized public-coin communication complexity of f. This matches the lower bound shown previously while the best previously known upper bound was doubly exponential in c. Our schemes reveal a new connection between common randomness and unbiased error-correcting codes, e.g., dual-BCH codes and their analogues in Euclidean space.