Title: Non interactive simulation of correlated distributions is decidable,
Abstract: 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{á}cs-K{ö}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.