About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Conference paper
Improved bounds on interactive communication
Abstract
(X, Y) is a pair of random variables. Person Px knows X, Person Py knows Y, and both know the joint probability distribution of (X, Y). Using a predetermined protocol, they exchange messages over a binary, error-free, channel in order for Py to learn X. Px may or may not learn Y.Ĉm(X|Y) is the number of information bits that must be transmitted (by both persons) in the worst case if only m messages are allowed. Ĉ∞(X|Y) is the corresponding number of bits when there is no restriction on the number of messages exchanged. It is known that one-message communication may require exponentially more bits than the minimum possible: for some (X, Y) pairs, Ĉ(X|Y) = 2Ĉ∞(X|Y)-1. Yet just two messages suffice to reduce communication to almost the minimum: for all (X, Y) pairs, Ĉ2(X|Y) ≤ 4Ĉ∞(X|Y)+3. It was further shown that for any positive ϵ there are (X,Y) pairs satisfying Ĉ2(X\Y) ≥ (2 - ϵ)Ĉ∞(X|Y). An obvious open problem is whether there is an m such that m messages are asymptotically optimal: Ĉm(X|Y) ≤ Ĉ∞(X|Y) + o(Ĉ∞(X|Y)) for all (X,Y) pairs. We improve the above bounds, thereby stepping towards a resolution of the open problem. We show that for all (X, Y) pairs, Ĉ2(X|Y) ≤ eĈ∞(X|Y) + 7 and that Ĉ4(X|Y) < 2Ĉ∞(X|Y) + 3.2 log Ĉ∞(X|Y) + 4. The proofs improve known techniques for both lower- and upper-bounds.
Related
Conference paper
Unassisted true analog neural network training chip
Conference paper