Non interactive simulation of correlated distributions is decidable
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 distribution...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Society for Industrial and Applied Mathematics
2018
|
| Online Access: | http://hdl.handle.net/1721.1/116201 |
| _version_ | 1811071573298249728 |
|---|---|
| author | De, Anindya Neeman, Joe Mossel, Elchanan |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics De, Anindya Neeman, Joe Mossel, Elchanan |
| author_sort | De, Anindya |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T08:53:18Z |
| format | Article |
| id | mit-1721.1/116201 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T08:53:18Z |
| publishDate | 2018 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/1162012022-09-30T11:55:23Z Non interactive simulation of correlated distributions is decidable De, Anindya Neeman, Joe Mossel, Elchanan Massachusetts Institute of Technology. Department of Mathematics Mossel, Elchanan 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. United States. Office of Naval Research (rant N00014-16-1-2227) National Science Foundation (U.S.). Division of Computing and Communication Foundations (1665252) National Science Foundation (U.S.). Division of Mathematical Sciences (737944) 2018-06-11T15:11:36Z 2018-06-11T15:11:36Z 2018-01 2018-05-29T16:12:22Z Article http://purl.org/eprint/type/ConferencePaper 0368-4245 http://hdl.handle.net/1721.1/116201 De, Anindya, Elchanan Mossel, and Joe Neeman. “Non Interactive Simulation of Correlated Distributions Is Decidable.” Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (January 2018): 2728–2746. http://dx.doi.org/10.1137/1.9781611975031.174 Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics SIAM |
| spellingShingle | De, Anindya Neeman, Joe Mossel, Elchanan Non interactive simulation of correlated distributions is decidable |
| title | Non interactive simulation of correlated distributions is decidable |
| title_full | Non interactive simulation of correlated distributions is decidable |
| title_fullStr | Non interactive simulation of correlated distributions is decidable |
| title_full_unstemmed | Non interactive simulation of correlated distributions is decidable |
| title_short | Non interactive simulation of correlated distributions is decidable |
| title_sort | non interactive simulation of correlated distributions is decidable |
| url | http://hdl.handle.net/1721.1/116201 |
| work_keys_str_mv | AT deanindya noninteractivesimulationofcorrelateddistributionsisdecidable AT neemanjoe noninteractivesimulationofcorrelateddistributionsisdecidable AT mosselelchanan noninteractivesimulationofcorrelateddistributionsisdecidable |