Non interactive simulation of correlated distributions is decidable

zbMATH Open1417.94025arXiv1701.01485MaRDI QIDQ4608069FDOQ4608069

Authors: Anindya De, Elchanan Mossel, Joe Neeman 

Publication date: 15 March 2018

Abstract: A basic problem in information theory is the following: Let $mathbfP=(mathbfX,mathbfY)$ be an arbitrary distribution where the marginals $mathbfX$ and $mathbfY$ are (potentially) correlated. Let Alice and Bob be two players where Alice gets samples ${x_i}_{ige1}$ and Bob gets samples ${y_i}_{ige1}$ and for all $i$, $(x_i,y_i)simmathbfP$. What joint distributions $mathbfQ$ can be simulated by Alice and Bob without any interaction? Classical works in information theory by G{'a}cs-K{"o}rner and Wyner answer this question when at least one of $mathbfP$ or $mathbfQ$ is the distribution on $0,1imes0,1$ where each marginal is unbiased and identical. 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 $mathbfQ$ supported on $0,1imes0,1$. We extend their result to $mathbfQ$ supported on any finite alphabet. We rely on recent results in Gaussian geometry (by the authors) as well as a new emph{smoothing argument} inspired by the method of emph{boosting} from learning theory and potential function arguments from complexity theory and additive combinatorics.

Full work available at URL: https://arxiv.org/abs/1701.01485

Recommendations

• Secure non-interactive simulation from arbitrary joint distributions
• LATIN 2004: Theoretical Informatics
• On the (im)possibility of non-interactive correlation distillation
• Optimality of correlated sampling strategies
• Communication complexity of estimating correlations

Mathematics Subject Classification ID

Probability distributions: general theory (60E05) Statistical aspects of information-theoretic topics (62B10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Information theory (general) (94A15) Quantum coherence, entanglement, quantum correlations (81P40)

Cited In (10)

• Secure non-interactive simulation from arbitrary joint distributions
• Dimension Reduction for Polynomials over Gaussian Space and Applications
• Three candidate plurality is stablest for small correlations
• One-message secure reductions: on the cost of converting correlations
• Secure non-interactive reduction and spectral analysis of correlations
• Simulating (log ^c n )-wise independence in NC
• Optimality of correlated sampling strategies
• Secure non-interactive simulation: feasibility and rate
• Nonlocal Games with Noisy Maximally Entangled States are Decidable
• Secure non-interactive reducibility is decidable

This page was built for publication: Non interactive simulation of correlated distributions is decidable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608069)