Non interactive simulation of correlated distributions is decidable

Anindya De, Elchanan Mossel, Joe Neeman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

Abstract

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.

Original languageEnglish (US)
Title of host publication29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
EditorsArtur Czumaj
PublisherAssociation for Computing Machinery
Pages2728-2746
Number of pages19
ISBN (Electronic)9781611975031
DOIs
StatePublished - Jan 1 2018
Event29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 - New Orleans, United States
Duration: Jan 7 2018Jan 10 2018

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
CountryUnited States
CityNew Orleans
Period1/7/181/10/18

Fingerprint

Interactive Simulation
Information theory
Information Theory
Additive Combinatorics
Learning Theory
Complexity Theory
Boosting
Potential Function
Joint Distribution
Smoothing
Geometry
Arbitrary
Interaction
Simulation

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

De, A., Mossel, E., & Neeman, J. (2018). Non interactive simulation of correlated distributions is decidable. In A. Czumaj (Ed.), 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 (pp. 2728-2746). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery. https://doi.org/10.1137/1.9781611975031.174
De, Anindya ; Mossel, Elchanan ; Neeman, Joe. / Non interactive simulation of correlated distributions is decidable. 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. editor / Artur Czumaj. Association for Computing Machinery, 2018. pp. 2728-2746 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
@inproceedings{33acd3a515984287a48049c3167214b2,
title = "Non interactive simulation of correlated distributions is decidable",
abstract = "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{\"o}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.",
author = "Anindya De and Elchanan Mossel and Joe Neeman",
year = "2018",
month = "1",
day = "1",
doi = "10.1137/1.9781611975031.174",
language = "English (US)",
series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "Association for Computing Machinery",
pages = "2728--2746",
editor = "Artur Czumaj",
booktitle = "29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018",

}

De, A, Mossel, E & Neeman, J 2018, Non interactive simulation of correlated distributions is decidable. in A Czumaj (ed.), 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 2728-2746, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, United States, 1/7/18. https://doi.org/10.1137/1.9781611975031.174

Non interactive simulation of correlated distributions is decidable. / De, Anindya; Mossel, Elchanan; Neeman, Joe.

29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. ed. / Artur Czumaj. Association for Computing Machinery, 2018. p. 2728-2746 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Non interactive simulation of correlated distributions is decidable

AU - De, Anindya

AU - Mossel, Elchanan

AU - Neeman, Joe

PY - 2018/1/1

Y1 - 2018/1/1

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

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

ER -

De A, Mossel E, Neeman J. Non interactive simulation of correlated distributions is decidable. In Czumaj A, editor, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. Association for Computing Machinery. 2018. p. 2728-2746. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). https://doi.org/10.1137/1.9781611975031.174