Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality (Q2472722)

This note deals with so-called problem of non-interactive correlation distillation (NICD). In its most general form the problem involves \(k\) players who receive noisy copies of a uniformly random bit string of length \(n\). The players wish to agree on a single random bit but are not allowed to communicate. The problem is to understand the extent to which the players can successfully distill the correlations in their strings into a shared random bit. This problem is relevant for cryptographic information reconciliation, random beacons in cryptography and security, and coding theory. The paper contains the following new results: In the case of a \(k\)-leaf star graph they resolve the open question of whether the success probability must go to zero as \(k\to \infty\). The authors show that is indeed the case and provide matching upper and lower bounds on the asymptotically optimal rate(a slowly-decaying polynomial). In the case of the \(k\)-vertex path graph, they show that it is always optimal for all players to use the same 1-bit function. In the general case it is shown that all players should use monotone functions. They also show, somewhat surprisingly, that for certain trees it is better if not all players use the same function.