Decidability of Non-interactive Simulation of Joint Distributions

By Badih Ghazi, Pritish Kamath, Madhu Sudan. 2016

35 citations recorded by the source corpus.

We 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 Yn respectively where {(Xi, Yi)}ni = 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.

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): “…x 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…”
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].”
Non interactive simulation of correlated distributions is decidable (2017, background): “In a recent paper, Ghazi, Kamath, and Sudan [GKS16] proved Theorems 1.1 and 1.2 in the case k = 2 .”