### 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 language | English (US) |
---|---|

Title of host publication | 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 |

Editors | Artur Czumaj |

Publisher | Association for Computing Machinery |

Pages | 2728-2746 |

Number of pages | 19 |

ISBN (Electronic) | 9781611975031 |

DOIs | |

State | Published - Jan 1 2018 |

Event | 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 - New Orleans, United States Duration: Jan 7 2018 → Jan 10 2018 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

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

Country | United States |

City | New Orleans |

Period | 1/7/18 → 1/10/18 |

### Fingerprint

### ASJC Scopus subject areas

- Software
- Mathematics(all)

### Cite this

*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

}

*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.

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 -