Communication with Imperfectly Shared Randomness

Clément L. Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan

TL;DR

This paper explores how communication complexity is affected when parties share "imperfect" randomness, meaning their random bits are correlated but not identical. They show that while perfect shared randomness offers significant savings, imperfectly shared randomness still provides benefits over no shared randomness, though often at a higher cost. The work introduces new problems and techniques to bridge the gap between these two models.

What Problem Does This Paper Address?

In communication complexity, shared randomness is a powerful tool that can drastically reduce the number of bits needed for parties to compute a function. For example, testing if two strings are identical deterministically takes $n$ bits, but with shared randomness, it can be done in $O(1)$ bits. However, in real-world scenarios, perfect shared randomness is often unrealistic. Instead, parties might have correlated random sources, like two people trying to recall a shared experience – they have related but not identical memories. This paper investigates how communication complexity changes when parties have access to such imperfectly shared randomness, specifically focusing on the gap between perfect shared randomness and private randomness. They aim to understand if the benefits of shared randomness can be retained to some degree even without perfect correlation.

Methods

The paper introduces a formal model for imperfectly shared randomness, where Alice and Bob's random bits are correlated according to a parameter $p \in [-1, 1]$. They then explore several key problems:

  • Uncertain Compression: Alice has a distribution $P$ and a message $m$, while Bob has a "close" distribution $Q$. They want to communicate $m$ with minimal bits. The paper shows that imperfectly shared randomness allows compression close to the entropy $H(P)$, similar to the perfectly shared case.
  • Agreement Distillation: Alice and Bob want to extract a small number of perfectly agreed-upon random bits from their correlated sources. They show that some savings are possible with imperfect randomness, but these savings are limited.
  • General Connection: A core contribution is establishing a general relationship between communication complexity with perfect shared randomness (PSR) and imperfectly shared randomness (ISR). They introduce a "hard" problem called GAPINNERPRODUCT and show that any problem solvable with $k$ bits of PSR can be solved with $O(\text{poly}(k))$ bits of ISR. Crucially, they also prove a matching lower bound for a related problem, SPARSEGAPINNERPRODUCT, showing that ISR can require exponentially more communication than PSR for certain problems.
  • Technical Tools: The proofs rely on advanced techniques from theoretical computer science, including:
  • Small-set expansion of the noisy hypercube: Used for lower bounds in agreement distillation.
  • Invariance principle: A key tool that allows transferring results from discrete, correlated random variables to continuous Gaussian variables, simplifying analysis. This is used to prove the general connection between PSR and ISR.
  • Vector representation of strategies: Communication protocols are represented as vectors in convex sets, enabling the use of geometric and analytical tools.

Datasets

Not discussed in the paper. The paper deals with theoretical communication complexity and does not involve empirical evaluation on datasets.

Key Insights and Ideas

  • Imperfect randomness is still useful: While not as powerful as perfect shared randomness, imperfectly shared randomness still offers advantages over having no shared randomness at all.
  • The gap can be exponential: For certain problems, the communication complexity with imperfectly shared randomness can be exponentially higher than with perfectly shared randomness. This highlights that the "quality" of shared randomness matters significantly.
  • "Low influence" is key: The paper connects communication complexity with the concept of "influence" of variables in Boolean functions. Strategies that rely on low-influence variables are more robust to noise in randomness, but this robustness comes at a communication cost.
  • Invariance principle as a bridge: The invariance principle is a powerful technique that allows bridging the gap between discrete, noisy settings and continuous, cleaner Gaussian settings, simplifying complex proofs.

Key Results

  • Uncertain Compression: For any distribution $P$ with entropy $H(P) < l$, the communication complexity is $O(H(P) + \Delta)$, where $\Delta$ relates to the difference between the distributions.
  • Agreement Distillation: For $k$ bits of entropy, the communication complexity is $O(k)$ with imperfect randomness, but the savings over the naive protocol are limited by the correlation parameter $p$. Specifically, for $p < 1$, the complexity is at least $\epsilon k - \log(1/\gamma)$ for some $\epsilon > 0$.
  • General Connection (Upper Bound): Any problem with communication complexity $k$ using perfectly shared randomness can be solved with $O(\text{poly}(k))$ bits using imperfectly shared randomness.
  • General Connection (Lower Bound): There exists a promise problem solvable with $k$ bits of PSR that requires $2^{\Omega(k)}$ bits with imperfectly shared randomness. This is a major result showing the fundamental difference between the two models.

Limitations and Future Work

  • Two-sided error: The protocols presented generally have two-sided error, meaning they can err on both yes and no instances. The authors note that it's an open question whether one-sided error offers any benefits in the imperfectly shared randomness setting.
  • Specific correlation model: The paper focuses on a specific model of $p$-correlated random bits. Generalizing to other forms of correlated randomness could be a future direction.
  • Generalizing Newman's Theorem: Newman's theorem shows that $O(\log n)$ bits of private randomness suffice for many problems. It's unclear if a similar logarithmic bound exists for imperfectly shared randomness.
  • Input length $n$: The paper studies problems where communication complexity is ideally independent of input size $n$. Extending these results to scenarios where $n$ plays a more direct role in communication could be interesting.
  • More general functions: The paper focuses on specific problems. Investigating the power of imperfectly shared randomness for a broader class of functions would be valuable.

Summary updated

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.
BibTeX
@misc{canonne2014communication,
  author = {Clément L. Canonne and Venkatesan Guruswami and Raghu Meka and Madhu Sudan},
  title = {{Communication with Imperfectly Shared Randomness}},
  year = {2014},
  eprint = {1411.3603},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1411.3603},
}

Loading related content...

Figure