On Non-Interactive Simulation of Binary Random Variables

DOI10.1109/TIT.2021.3054659MaRDI QIDQ5001647zbMATH OpenOpenAlexFDO

Authors Lei Yu, Vincent Y. F. Tan

Publication date 22 July 2021

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

zbMATH Keywords

average distanceboundsdistance enumerator of binary block codesnon-interactive simulation of binary random variables

Mathematics Subject Classification ID

Combinatorial probability (60C99) Characteristic functions; other transforms (60E10) Inequalities; stochastic orderings (60E15) Linear codes (general theory) (94B05)

Abstract: We leverage proof techniques Fourier analysis and an existing result in coding theory to derive new bounds for the problem of non-interactive simulation of binary random variables. Previous bounds in the literature were derived by applying data processing inequalities concerning maximal correlation or hypercontractivity. We show that our bounds are sharp in some regimes. For a specific instance of problem parameters, our main result answers an open problem posed by E. Mossel in 2017. As by-products of our analyses, various new properties of the average distance and distance enumerator of binary block codes are established.

Cited in

(5)

• Edge-isoperimetric inequalities and ball-noise stability: linear programming and probabilistic approaches
• Simulating (log ^c n )-wise independence in NC
• Probabilistic view of voting, paradoxes, and manipulation
• Common Information, Noise Stability, and Their Extensions
• On the \(\Phi \)-stability and related conjectures

This page was built for publication: On Non-Interactive Simulation of Binary Random Variables

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