We consider the following non-interactive simulation problem: Alice and Bob observe sequences Xnand Yn, respectively, where ((Xi, Yi)}i=1nare drawn independent identically distributed from P(x, y), and they output U and V, respectively, which is required to have a joint law that is close in total variation to a specified Q(u, v). It is known that the maximal correlation of U and V must necessarily be no bigger than that of X and Y if this is to be possible. Our main contribution is to bring hypercontractivity to bear as a tool on this problem. In particular, we show that if P(x, y) is the doubly symmetric binary source, then hypercontractivity provides stronger impossibility results than maximal correlation. Finally, we extend these tools to provide impossibility results for the k-agent version of this problem.
We consider the following non-interactive simulation problem: Alice and Bob observe sequences Xnand Yn, respectively, where ((Xi, Yi)}i=1nare drawn independent identically distributed from P(x, y), and they output U and V, respectively, which is required to have a joint law that is close in total variation to a specified Q(u, v). It is known that the maximal correlation of U and V must necessarily be no bigger than that of X and Y if this is to be possible. Our main contribution is to bring hypercontractivity to bear as a tool on this problem. In particular, we show that if P(x, y) is the doubly symmetric binary source, then hypercontractivity provides stronger impossibility results than maximal correlation. Finally, we extend these tools to provide impossibility results for the k-agent version of this problem.
We consider the following problem: Alice and Bob observe sequences Xnand Ynrespectively where {(Xi, Yi)}i=1∞are drawn i.i.d. from P(x, y), and they output U and V respectively which is required to have a joint law that is close in total variation to a specified Q(u, v). One important technique to establish impossibility results for this problem is the Hirschfeld-Gebelein-Rényi maximal correlation which was considered by Witsen-hausen [1]. Hypercontractivity studied by Ahlswede and Gács [2] and reverse hypercontractivity recently studied by Mossel et al. [3] provide another approach for proving impossibility results. We consider the tightest impossibility results that can be obtained using hypercontractivity and reverse hypercontractivity and provide a necessary and sufficient condition on the source distribution P(x, y) for when this approach subsumes the maximal correlation approach. We show that the binary pair source distribution with symmetric noise satisfies this condition.
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.
We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequences Unand Vnrespectively, drawn from a joint distribution pUV⊗n, and wish to locally generate sequences Xnand Ynrespectively with a joint distribution that is close (in KL divergence) to pXY⊗n. We provide a single-letter condition under which such a simulation is asymptotically possible with a vanishing KL divergence. Our condition is nontrivial only in the case where the Gàcs-Körner (GK) common information between U and V is nonzero, and we conjecture that only scalar Markov chains X−U−V−Y can be simulated otherwise. Motivated by this conjecture, we further examine the case where both pUVand pXYare doubly symmetric binary sources with parameters p,q≤1/2 respectively. While it is trivial that in this case p≤q is both necessary and sufficient, we show that when p is close to q then any successful simulation is close to being scalar in the total variation sense.
We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequencesUnandVnrespectively, drawn from a joint distributionpUV⊗n, and wish to locally generate sequencesXnandYnrespectively with a joint distribution that is close (in KL divergence) topXY⊗n. We provide a single-letter condition under which such a simulation is asymptotically possible with a vanishing KL divergence. Our condition is nontrivial only in the case where the Gàcs-Körner (GK) common information betweenUandVis nonzero, and we conjecture that only scalar Markov chainsX−U−V−Ycan be simulated otherwise. Motivated by this conjecture, we further examine the case where bothpUVandpXYare doubly symmetric binary sources with parametersp,q≤1/2respectively. While it is trivial that in this casep≤qis both necessary and sufficient, we use Fourier analytic tools to show that whenpis close toqthen any successful simulation is close to being scalar in the total variation sense.
A basic problem in information theory is the following: Let P = (X, Y) be an arbitrary distribution where the marginals X and Y are (potentially) correlated. Let Alice and Bob be two players where Alice gets samples {xi}i≥1 and Bob gets samples {yi}i≥i and for all i, (xi,yi) ∼ P. What joint distributions 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 P or Q is the distribution Eq (Eq is defined as uniform over the points (0, 0) and (1, 1)). 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 Q supported on {0, 1} × {0, 1}. We extend their result to Q supported on any finite alphabet. Moreover, we show that If Q can be simulated, our algorithm also provides a (non-interactive) simulation protocol. We rely on recent results in Gaussian geometry (by the authors) as well as a new smoothing argument inspired by the method of boosting from learning theory and potential function arguments from complexity theory and additive combinatorics.
This work presents a Fourier analysis framework for the non-interactive source simulation (NISS) problem. Two distributed agents observe a pair of sequencesXdandYddrawn according to a joint distributionPXdYd. The agents aim to generate outputsU=fd(Xd)andV=gd(Yd)with a joint distribution sufficiently close in total variation to a target distributionQUV. Existing works have shown that the NISS problem with finite-alphabet outputs is decidable. For the binary-output NISS, an upper-bound to the input complexity was derived which isO(exppoly(ϵ1)). In this work, the input complexity and algorithm design are addressed in several classes of NISS scenarios. For binary-output NISS scenarios with doubly-symmetric binary inputs, it is shown that the input complexity isΘ(logϵ1), thus providing a super-exponential improvement in input complexity. An explicit characterization of the simulating pair of functions is provided. For general finite-input scenarios, a constructive algorithm is introduced that explicitly finds the simulating functions(fd(Xd),gd(Yd)). The approach relies on a novel Fourier analysis framework. Various numerical simulations of NISS scenarios with IID inputs are provided. Furthermore, to illustrate the general applicability of the Fourier framework, several examples with non-IID inputs, including entanglement-assisted NISS and NISS with Markovian inputs are provided.