research-article

Non interactive simulation of correlated distributions is decidable

Authors:

Elchanan Mossel,

Joe NeemanAuthors Info & Claims

SODA '18: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms

Pages 2728 - 2746

Published: 07 January 2018 Publication History

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 {x_i}_i≥1 and Bob gets samples {y_i}_i≥1 and for all i, (x_i, y_i) ∼ P. What joint distributions Q can be simulated by Alice and Bob without any interaction?

Classical works in information theory by Gács-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 {0, 1} × {0, 1}. 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.

References

[1]

{AC93} R. Ahlswede and I. Csiszár. Common randomness in information theory and cryptography - I: Secret sharing. IEEE Trans. Information Theory, 39(4):1121--1132, 1993.

Digital Library

[2]

{AC98} R. Ahlswede and I. Csiszár. Common Randomness in Information Theory and Cryptography - Part II: CR Capacity. IEEE Trans. Information Theory, 44(1):225--240, 1998.

Digital Library

[3]

{AL06} N. Alon and E. Lubetzky. The shannon capacity of a graph and the independence numbers of its powers. IEEE Transactions on Information Theory, 52(5):2172--2176, 2006.

Digital Library

[4]

{BGI14} M. Bavarian, D. Gavinsky, and T. Ito. On the Role of Shared Randomness in Simultaneous Communication. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, pages 150--162, 2014.

[5]

{Bor85} C. Borell. Geometric bounds on the Ornstein-Uhlenbeck velocity process. Probability Theory and Related fields, 70:1--13, 1985.

[6]

{CG59} Ward Cheney and Allen A Goldstein. Proximity maps for convex sets. Proceedings of the American Mathematical Society, 10(3):448--450, 1959.

[7]

{CGMS15} C. Canonne, V. Guruswami, R. Meka, and M. Sudan. Communication with Imperfectly Shared Randomness. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 257--262, 2015.

Digital Library

[8]

{CN00} I. Csiszár and P. Narayan. Common randomness and secret key generation with a helper. IEEE Trans. Information Theory, 46(2):344--366, 2000.

Digital Library

[9]

{CW01} A. Carbery and J. Wright. Distributional and L^q norm inequalities for polynomials over convex bodies in Rⁿ. Mathematical Research Letters, 8(3):233--248, 2001.

[10]

{DDFS14} A. De, I. Diakonikolas, V. Feldman, and R. Servedio. Near-optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces. Journal of the ACM, 61(2), 2014.

Digital Library

[11]

{DDS14} Anindya De, Ilias Diakonikolas, and Rocco A. Servedio. Deterministic approximate counting for juntas of degree-2 polynomial threshold functions. In IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11--13, 2014, pages 229--240, 2014.

Digital Library

[12]

{DLTW08} A. Doherty, Y. Liang, B. Toner, and S. Wehner. The quantum moment problem and bounds on entangled multi-prover games. In Computational Complexity, 2008. CCC'08. 23rd Annual IEEE Conference on, pages 199--210. IEEE, 2008.

Digital Library

[13]

{DMN17} A. De, E. Mossel, and J. Neeman. Noise stability is computable and low-dimensional. In Conference on Computational Complexity, pages 28:1--28:10, 2017. Full version available at https://arxiv.org/abs/1701.01483.

[14]

{DS14} A. De and R. Servedio. Efficient deterministic approximate counting for low-degree polynomial threshold functions. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, pages 832--841, 2014. Full version at http://arxiv.org/abs/1311.7178.

Digital Library

[15]

{DSTW10} I. Diakonikolas, R. Servedio, L.-Y. Tan, and A. Wan. A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions. In CCC, pages 211--222, 2010.

Digital Library

[16]

{FK99} A. Frieze and R. Kannan. Quick approximation to matrices and applications. Combinatorica, 19(2):175--220, 1999.

[17]

{Fre95} Y. Freund. Boosting a weak learning algorithm by majority. Information and Computation, 121(2):256--285, 1995.

Digital Library

[18]

{GK73} P. Gács and J. Körner. Common information is far less than mutual information. Problems of Control and Information Theory, 2(2):149--162, 1973.

[19]

{GKR17} B. Ghazi, P. Kamath, and P. Raghavendra. Dimension Reduction for Polynomials over Gaussian Space and Applications. arXiv preprint arXiv:1708.03808, 2017.

[20]

{GKS16a} B. Ghazi, P. Kamath, and M. Sudan. Communication Complexity of Permutation-Invariant Functions. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pages 1902--1921, 2016.

Digital Library

[21]

{GKS16b} B. Ghazi, P. Kamath, and M. Sudan. Decidability of Non-Interactive Simulation of Joint Distributions. In 56th Annual IEEE Symposium on Foundations of Computer Science, pages 545--554, 2016.

[22]

{Hae79} W. Haemers. On some problems of Lovász concerning the Shannon capacity of a graph. IEEE Transactions on Information Theory, 25(2):231--232, 1979.

Digital Library

[23]

{Imp95} R. Impagliazzo. Hard-Core Distributions for Somewhat Hard Problems. In 36th Annual Symposium on Foundations of Computer Science, pages 538--545, 1995.

Digital Library

[24]

{Jan97} S. Janson. Gaussian Hilbert Spaces. Cambridge University Press, Cambridge, UK, 1997.

[25]

{KA16} S. Kamath and V. Anantharam. On non-interactive simulation of joint distributions. IEEE Transactions on Information Theory, 62(6):3419--3435, 2016.

[26]

{KKM⁺ 11} J. Kempe, H. Kobayashi, K. Matsumoto, B. Toner, and T. Vidick. Entangled games are hard to approximate. SIAM Journal on Computing, 40(3):848--877, 2011.

Digital Library

[27]

{KNOW14} P. Kothari, A. Nayyeri, R. O'Donnell, and C. Wu. Testing surface area. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5--7, 2014, pages 1204--1214, 2014.

Digital Library

[28]

{Lov79} L. Lovász. On the shannon capacity of a graph. IEEE Transactions on Information theory, 25(1):1--7, 1979.

Digital Library

[29]

{LRS15} J. Lee, P. Raghavendra, and D. Steurer. Lower Bounds on the Size of Semidefinite Programming Relaxations. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, pages 567--576, 2015.

Digital Library

[30]

{MO05} E. Mossel and R. O'Donnell. Coin flipping from a cosmic source: On error correction of truly random bits. Random Structures Algorithms, 26(4):418--436, 2005.

Digital Library

[31]

{MOO10} E. Mossel, R. O'Donnell, and K. Oleszkiewicz. Noise stability of functions with low influences: Invariance and optimality. Ann. Math., 171(1):295--341, 2010.

[32]

{MOR⁺ 06} E. Mossel, R. O'Donnell, O. Regev, J. Steif, and B. Sudakov. Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality. Israel J. Math., 154:299--336, 2006.

[33]

{Mos10} E. Mossel. Gaussian bounds for noise correlation of functions. Geometric and Functional Analysis, 19(6):1713--1756, 2010.

[34]

{Nee14} J. Neeman. Testing surface area with arbitrary accuracy. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 393--397, 2014.

Digital Library

[35]

{O'D14} R. O'Donnell. Analysis of Boolean functions. Cambridge University Press, Cambridge, 2014.

Digital Library

[36]

{Reg16} O. Regev. . Personal communication, 2016.

[37]

{Sch90} R. Schapire. The strength of weak learnability. Machine Learning, 5(2):197--227, 1990.

Digital Library

[38]

{Tao07} T. Tao. Structure and randomness in combinatorics. In Proc. 48th IEEE Symposium on Foundations of Computer Science (FOCS), 2007.

Digital Library

[39]

{TTV09} Luca Trevisan, Madhur Tulsiani, and Salil P. Vadhan. Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. In IEEE Conference on Computational Complexity, pages 126--136, 2009.

Digital Library

[40]

{Wit75} H. S. Witsenhausen. On Sequences of Pairs of Dependent Random Variables. SIAM Journal on Applied Mathematics, 28(1):100--113, 1975.

[41]

{Wyn75} A. Wyner. The common information of two dependent random variables. IEEE Transactions on Information Theory, 21(2):163--179, 1975.

Digital Library

Cited By

Bafna MGhazi BGolowich NSudan MChan T(2019)Communication-rounds tradeoffs for common randomness and secret key generationProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310547(1861-1871)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310547
Ghazi BKamath PRaghavendra PServedio R(2018)Dimension reduction for polynomials over gaussian space and applicationsProceedings of the 33rd Computational Complexity Conference10.5555/3235586.3235614(1-37)Online publication date: 22-Jun-2018
https://dl.acm.org/doi/10.5555/3235586.3235614

Non interactive simulation of correlated distributions is decidable
1. Theory of computation

Recommendations

Quantum teleportation with nonclassical correlated states in noninertial frames

Quantum teleportation is studied in noninertial frame, for fermionic case, when Alice and Bob share a general nonclassical correlated state. In noninertial frames, two fidelities of teleportation are given. It is found that the average fidelity of ...
A Representation for Ellipsoidal Distributions

Let $S_n ( {\boldsymbol \theta} ,{\boldsymbol \Omega} )$ be the class of distributions on $\mathcal{R}^n $ having density functions $f( {\bf x} ) = \psi ( {( {\bf x} - {\bf \theta } )^\prime {\boldsymbol \Omega} ^{ - 1} ( {{\bf x} - {\boldsymbol \theta} ...
Comparing Wigner, Husimi and Bohmian distributions: which one is a true probability distribution in phase space?

The Wigner distribution function is a quasi-probability distribution. When properly integrated, it provides the correct charge and current densities, but it gives negative probabilities in some points and regions of the phase space. Alternatively, the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '18: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms

January 2018

2859 pages

ISBN:9781611975031

Program Chair:
Artur Czumaj
University of Warwick, United Kingdom

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 07 January 2018

Check for updates

Qualifiers

Research-article

Conference

SODA '18

Sponsor:

SIGACT

SODA '18: Symposium on Discrete Algorithms

January 7 - 10, 2018

Louisiana, New Orleans

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
35
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bafna MGhazi BGolowich NSudan MChan T(2019)Communication-rounds tradeoffs for common randomness and secret key generationProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310547(1861-1871)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310547
Ghazi BKamath PRaghavendra PServedio R(2018)Dimension reduction for polynomials over gaussian space and applicationsProceedings of the 33rd Computational Complexity Conference10.5555/3235586.3235614(1-37)Online publication date: 22-Jun-2018
https://dl.acm.org/doi/10.5555/3235586.3235614

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents