%AGhazi, Badih%AKamath, Pritish%ASudan, Madhu%D2016%I
%K
%MOSTI ID: 10026315
%PMedium: X
%TDecidability of Non-Interactive Simulation of Joint Distributions
%XWe present decidability results for a sub-class
of “non-interactive” simulation problems, a well-studied
class of problems in information theory. A non-interactive
simulation problem is specified by two distributions P(x, y)
and Q(u, v): The goal is to determine if two players, Alice
and Bob, that observe sequences Xn and Y n respectively
where {(Xi, Yi)}n
i=1 are drawn i.i.d. from P(x, y) can
generate pairs U and V respectively (without communicating
with each other) with a joint distribution that is
arbitrarily close in total variation to Q(u, v). Even when
P and Q are extremely simple: e.g., P is uniform on the
triples {(0, 0), (0, 1), (1, 0)} and Q is a “doubly symmetric
binary source”, i.e., U and V are uniform ±1 variables
with correlation say 0.49, it is open if P can simulate Q.
In this work, we show that whenever P is a distribution
on a finite domain and Q is a 2 × 2 distribution, then
the non-interactive simulation problem is decidable: specifically,
given δ > 0 the algorithm runs in time bounded by
some function of P and δ and either gives a non-interactive
simulation protocol that is δ-close to Q or asserts that no
protocol gets O(δ)-close to Q. The main challenge to such
a result is determining explicit (computable) convergence
bounds on the number n of samples that need to be drawn
from P(x, y) to get δ-close to Q. We invoke contemporary
results from the analysis of Boolean functions such as the
invariance principle and a regularity lemma to obtain such
explicit bounds.