Back to Search Start Over

Communication With Imperfectly Shared Randomness.

Authors :
Canonne, Clement L.
Guruswami, Venkatesan
Meka, Raghu
Sudan, Madhu
Source :
IEEE Transactions on Information Theory. Oct2017, Vol. 63 Issue 10, p6799-6818. 20p.
Publication Year :
2017

Abstract

Communication complexity investigates the amount of communication needed for two or more players to determine some joint function of their private inputs. For many interesting functions, the communication complexity can be much smaller than basic information theoretic measures associated with the players’ inputs such as the input length, the entropy, or even the conditional entropy. Communication complexity of many functions reduces further when the players share randomness. Classical works studied the communication complexity of functions when the interacting players share randomness perfectly, i.e., they get identical copies of randomness from a common source. This paper considers the variant of this question when the players share randomness imperfectly, i.e., when they get noisy copies of the randomness produced by some common source. Our main result shows that any function that can be computed by a $k$ -bit protocol in the perfect sharing model has a 2^{k} -bit protocol in the setting of imperfectly shared randomness and such an exponential growth is necessary. Our upper bound relies on ideas from locality sensitive hashing, while lower bounds rely on hypercontractivity and a new invariance principle tailored for communication protocols. [ABSTRACT FROM PUBLISHER]

Details

Language :
English
ISSN :
00189448
Volume :
63
Issue :
10
Database :
Academic Search Index
Journal :
IEEE Transactions on Information Theory
Publication Type :
Academic Journal
Accession number :
125207049
Full Text :
https://doi.org/10.1109/TIT.2017.2734103