Bounds on the Average Distance and Distance Enumerator with Applications to Non-Interactive Simulation.
Lei Yu, Vincent Y. F. Tan · arXiv (Cornell University) · 2019
We leverage proof techniques in coding theory and Fourier analysis to derive new bounds for the problem of non-interactive simulation of 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, and are also tighter than the existing ones in some other regimes. As by-products of our analyses, various new properties of the average distance and distance enumerator of binary block codes are established. Finally, by using an existing hypercontractivity bound for non-interactive simulation, a new bound on the average distance is derived.