TY - GEN

T1 - Non interactive simulation of correlated distributions is decidable

AU - De, Anindya

AU - Mossel, Elchanan

AU - Neeman, Joe

N1 - Publisher Copyright:
© Copyright 2018 by SIAM.

PY - 2018

Y1 - 2018

N2 - 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 fxigi1 and Bob gets samples fyigi1 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 Gacs-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 f0; 1gf0; 1g. 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.

AB - 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 fxigi1 and Bob gets samples fyigi1 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 Gacs-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 f0; 1gf0; 1g. 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.

UR - http://www.scopus.com/inward/record.url?scp=85045543154&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85045543154&partnerID=8YFLogxK

U2 - 10.1137/1.9781611975031.174

DO - 10.1137/1.9781611975031.174

M3 - Conference contribution

AN - SCOPUS:85045543154

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 2728

EP - 2746

BT - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

A2 - Czumaj, Artur

PB - Association for Computing Machinery

T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

Y2 - 7 January 2018 through 10 January 2018

ER -