Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR14-153 | 10th May 2016 20:22

Communication with Imperfectly Shared Randomness

RSS-Feed

Abstract:

The communication complexity of many fundamental problems reduces greatly
when the communicating parties share randomness that is independent of the
inputs to the communication task. Natural communication processes (say between
humans) however often involve large amounts of shared correlations among the
communicating players, but rarely allow for perfect sharing of randomness. Can
the communication complexity benefit from shared correlations as well as it
does from shared randomness? This question was considered mainly in the context
of simultaneous communication by Bavarian et al. (ICALP 2014). In this work we
study this problem in the standard interactive setting and give some general
results. In particular, we show that every problem with communication
complexity of $k$ bits with perfectly shared randomness has a protocol using
imperfectly shared randomness with complexity $\exp(k)$ bits. We also show that
this is best possible by exhibiting a promise problem with complexity $k$ bits
with perfectly shared randomness which requires $\exp(k)$ bits when the
randomness is imperfectly shared. Along the way we also highlight some other
basic problems such as compression, and agreement distillation, where shared
randomness plays a central role and analyze the complexity of these problems in
the imperfectly shared randomness model.

The technical highlight of this work is the lower bound that goes into the
result showing the tightness of our general connection. This result builds on
the intuition that communication with imperfectly shared randomness needs to be
less sensitive to its random inputs than communication with perfectly shared
randomness. The formal proof invokes results about the small-set expansion of
the noisy hypercube and an invariance principle to convert this intuition to a
proof, thus giving a new application domain for these fundamental results.



Changes to previous version:

Updated some references and discussion w.r.t. previous work


Revision #1 to TR14-153 | 18th November 2014 19:48

Communication with Imperfectly Shared Randomness


Abstract:

The communication complexity of many fundamental problems reduces greatly
when the communicating parties share randomness that is independent of the
inputs to the communication task. Natural communication processes (say between
humans) however often involve large amounts of shared correlations among the
communicating players, but rarely allow for perfect sharing of randomness. Can
the communication complexity benefit from shared correlations as well as it
does from shared randomness? This question was considered mainly in the context
of simultaneous communication by Bavarian et al. (ICALP 2014). In this work we
study this problem in the standard interactive setting and give some general
results. In particular, we show that every problem with communication
complexity of $k$ bits with perfectly shared randomness has a protocol using
imperfectly shared randomness with complexity $\exp(k)$ bits. We also show that
this is best possible by exhibiting a promise problem with complexity $k$ bits
with perfectly shared randomness which requires $\exp(k)$ bits when the
randomness is imperfectly shared. Along the way we also highlight some other
basic problems such as compression, and agreement distillation, where shared
randomness plays a central role and analyze the complexity of these problems in
the imperfectly shared randomness model.

The technical highlight of this work is the lower bound that goes into the
result showing the tightness of our general connection. This result builds on
the intuition that communication with imperfectly shared randomness needs to be
less sensitive to its random inputs than communication with perfectly shared
randomness. The formal proof invokes results about the small-set expansion of
the noisy hypercube and an invariance principle to convert this intuition to a
proof, thus giving a new application domain for these fundamental results.



Changes to previous version:

Updated the Agreement Distillation section, after being informed that the result Lemma 4.1 was already known in [2].


Paper:

TR14-153 | 14th November 2014 18:01

Communication with Imperfectly Shared Randomness





TR14-153
Authors: Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan
Publication: 14th November 2014 18:07
Downloads: 722
Keywords: 


Abstract:

The communication complexity of many fundamental problems reduces greatly
when the communicating parties share randomness that is independent of the
inputs to the communication task. Natural communication processes (say between
humans) however often involve large amounts of shared correlations among the
communicating players, but rarely allow for perfect sharing of randomness. Can
the communication complexity benefit from shared correlations as well as it
does from shared randomness? This question was considered mainly in the context
of simultaneous communication by Bavarian et al. (ICALP 2014). In this work we
study this problem in the standard interactive setting and give some general
results. In particular, we show that every problem with communication
complexity of $k$ bits with perfectly shared randomness has a protocol using
imperfectly shared randomness with complexity $\exp(k)$ bits. We also show that
this is best possible by exhibiting a promise problem with complexity $k$ bits
with perfectly shared randomness which requires $\exp(k)$ bits when the
randomness is imperfectly shared. Along the way we also highlight some other
basic problems such as compression, and agreement distillation, where shared
randomness plays a central role and analyze the complexity of these problems in
the imperfectly shared randomness model.

The technical highlight of this work is the lower bound that goes into the
result showing the tightness of our general connection. This result builds on
the intuition that communication with imperfectly shared randomness needs to be
less sensitive to its random inputs than communication with perfectly shared
randomness. The formal proof invokes results about the small-set expansion of
the noisy hypercube and an invariance principle to convert this intuition to a
proof, thus giving a new application domain for these fundamental results.



ISSN 1433-8092 | Imprint