Revision #2 Authors: Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan

Accepted on: 10th May 2016 20:22

Downloads: 236

Keywords:

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.

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

Revision #1 Authors: Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan

Accepted on: 18th November 2014 19:48

Downloads: 913

Keywords:

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.

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

TR14-153 Authors: Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan

Publication: 14th November 2014 18:07

Downloads: 754

Keywords:

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.