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