Abstract
In a recent work (Ghazi et al., SODA 2016), the authors with Komargodski and Kothari initiated the study of communication with contextual uncertainty, a setup aiming to understand how efficient communication is possible when the communicating parties imperfectly share a huge context. In this setting, Alice is given a function f and an input string x, and Bob is given a function g and an input string y. The pair (x,y) comes from a known distribution mu and f and g are guaranteed to be close under this distribution. Alice and Bob wish to compute g(x,y) with high probability. The lack of agreement between Alice and Bob on the function that is being computed captures the uncertainty in the context. The previous work showed that any problem with oneway communication complexity k in the standard model (i.e., without uncertainty, in other words, under the promise that f=g) has publiccoin communication at most O(k(1+I)) bits in the uncertain case, where I is the mutual information between x and y. Moreover, a lower bound of Omega(sqrt{I}) bits on the publiccoin uncertain communication was also shown.
However, an important question that was left open is related to the power that public randomness brings to uncertain communication. Can Alice and Bob achieve efficient communication amid uncertainty without using public randomness? And how powerful are publiccoin protocols in overcoming uncertainty? Motivated by these two questions:
 We prove the first separation between privatecoin uncertain communication and publiccoin uncertain communication. Namely, we exhibit a function class for which the communication in the standard model and the publiccoin uncertain communication are O(1) while the privatecoin uncertain communication is a growing function of n (the length of the inputs). This lower bound (proved with respect to the uniform distribution) is in sharp contrast with the case of publiccoin uncertain communication which was shown by the previous work to be within a constant factor from the certain communication. This lower bound also implies the first separation between publiccoin uncertain communication and deterministic uncertain communication. Interestingly, we also show that if Alice and Bob imperfectly share a sequence of random bits (a setup weaker than public randomness), then achieving a constant blowup in communication is still possible.
 We improve the lowerbound of the previous work on publiccoin uncertain communication. Namely, we exhibit a function class and a distribution (with mutual information I approx n) for which the oneway certain communication is k bits but the oneway publiccoin uncertain communication is at least Omega(sqrt{k}*sqrt{I}) bits.
Our proofs introduce new problems in the standard communication complexity model and prove lower bounds for these problems. Both the problems and the lower bound techniques may be of general interest.
BibTeX  Entry
@InProceedings{ghazi_et_al:LIPIcs:2017:7487,
author = {Badih Ghazi and Madhu Sudan},
title = {{The Power of Shared Randomness in Uncertain Communication}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {49:149:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7487},
URN = {urn:nbn:de:0030drops74871},
doi = {10.4230/LIPIcs.ICALP.2017.49},
annote = {Keywords: randomness, uncertainty, communication, imperfectly shared randomness, lower bounds}
}
Keywords: 

randomness, uncertainty, communication, imperfectly shared randomness, lower bounds 
Collection: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) 
Issue Date: 

2017 
Date of publication: 

07.07.2017 