Non interactive simulation of correlated distributions is decidable

By Anindya De, Elchanan Mossel, Joe Neeman. 2017

29 citations recorded by the source corpus.

A basic problem in information theory is the following: Let $\mathbf{P} = (\mathbf{X}, \mathbf{Y})$ be an arbitrary distribution where the marginals $\mathbf{X}$ and $\mathbf{Y}$ are (potentially) correlated. Let Alice and Bob be two players where Alice gets samples $\{x_i\}_{i \ge 1}$ and Bob gets samples $\{y_i\}_{i \ge 1}$ and for all $i$, $(x_i, y_i) \sim \mathbf{P}$. What joint distributions $\mathbf{Q}$ can be simulated by Alice and Bob without any interaction? Classical works in information theory by G{\'a}cs-K{\"o}rner and Wyner answer this question when at least one of $\mathbf{P}$ or $\mathbf{Q}$ is the distribution on $\{0,1\} \times \{0,1\}$ where each marginal is unbiased and identical. However, other than this special case, the answer to this question is understood in very few cases. Recently, Ghazi, Kamath and Sudan showed that this problem is decidable for $\mathbf{Q}$ supported on $\{0,1\} \times \{0,1\}$. We extend their result to $\mathbf{Q}$ supported on any finite alphabet. We rely on recent results in Gaussian geometry (by the authors) as well as a new \emph{smoothing argument} inspired by the method of \emph{boosting} from learning theory and potential function arguments from complexity theory and additive combinatorics.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Distributed Simulation and Distributed Inference (2018, background): “…and y respectively distributed according to p and q such that the probability that x = y is maximized; and non-interactive simulation [KA12, GKS16, DMN18], where two players, provided separately with samples from the marginals of a known distribution p , need to output samples U, V such that the…”
Inference Under Information Constraints II: Communication Constraints and Shared Randomness (2019, background): “Starting with [25] and [47] where the problem of generating shared randomness from correlated randomness and vice-versa, respectively, were considered, several important variants have been studied such as correlated sampling [11], [16], [34], [38] and noninteractive simulation [20], [27], [36].”