Non interactive simulation of correlated distributions is decidable

Anindya De, Elchanan Mossel, Joe Neeman

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

6 Scopus citations

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

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