TY - JOUR

T1 - Non-interactive correlation distillation, inhomogeneous markov chains, and the reverse bonami-beckner inequality

AU - Mossel, Elchanan

AU - O'Donnell, Ryan

AU - Regev, Oded

AU - Steif, Jeffrey E.

AU - Sudakov, Benny

N1 - Funding Information:
w Research supported in part by NSF grant DMS-0106589, DMS-0355497, and by an Alfred P. Sloan fellowship.
Funding Information:
* Supported by a Miller fellowship in Statistics and CS, U.C. Berkeley, by an Alfred P. Sloan fellowship in Mathematics, and by NSF grant DMS-0504245. ** Most of this work was done while the author was a student at Massachusetts Institute of Technology. This material is based upon work supported by the National Science Foundation under agreement No. CCR-0324906. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation. t Most of this work was done while the author was at the Institute for Advanced Study, Princeton, NJ. Work supported by an Alon Fellowship, ARO grant DAAD19-03-1-0082 and NSF grant CCR-9987845. :~ Supported in part by NSF grant DMS-0103841, the Swedish Research Council and the G5ran Gustafsson Foundation (KVA). Received August 27, 2004 and in revised form April 7, 2005

PY - 2006

Y1 - 2006

N2 - In this paper we study non-interactive correlation distillation (NICD), a generalization of noise sensitivity previously considered in [5, 31, 39]. We extend the model to NICD on trees. In this model there is a fixed undirected tree with players at some of the nodes. One node is given a uniformly random string and this string is distributed throughout the network, with the edges of the tree acting as independent binary symmetric channels. The goal of the players is to agree on a shared random bit without communicating. Our new contributions include the following: In the case of a fc-leaf star graph (the model considered in [31]), we resolve the open question of whether the success probability must go to zero as k → ∞. We show that this 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, we show that it is always optimal for all players to use the same 1-bit function. In the general case we show that all players should use monotone functions. We also show, somewhat surprisingly, that for certain trees it is better if not all players use the same function. Our techniques include the use of the reverse Bonami-Beckner inequality. Although the usual Bonami-Beckner has been frequently used before, its reverse counterpart seems not to be well known. To demonstrate its strength, we use it to prove a new isoperimetric inequality for the discrete cube and a new result on the mixing of short random walks on the cube. Another tool that we need is a tight bound on the probability that a Markov chain stays inside certain sets; we prove a new theorem generalizing and strengthening previous such bounds [2, 3, 6]. On the probabilistic side, we use the "reflection principle" and the FKG and related inequalities in order to study the problem on general trees.

AB - In this paper we study non-interactive correlation distillation (NICD), a generalization of noise sensitivity previously considered in [5, 31, 39]. We extend the model to NICD on trees. In this model there is a fixed undirected tree with players at some of the nodes. One node is given a uniformly random string and this string is distributed throughout the network, with the edges of the tree acting as independent binary symmetric channels. The goal of the players is to agree on a shared random bit without communicating. Our new contributions include the following: In the case of a fc-leaf star graph (the model considered in [31]), we resolve the open question of whether the success probability must go to zero as k → ∞. We show that this 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, we show that it is always optimal for all players to use the same 1-bit function. In the general case we show that all players should use monotone functions. We also show, somewhat surprisingly, that for certain trees it is better if not all players use the same function. Our techniques include the use of the reverse Bonami-Beckner inequality. Although the usual Bonami-Beckner has been frequently used before, its reverse counterpart seems not to be well known. To demonstrate its strength, we use it to prove a new isoperimetric inequality for the discrete cube and a new result on the mixing of short random walks on the cube. Another tool that we need is a tight bound on the probability that a Markov chain stays inside certain sets; we prove a new theorem generalizing and strengthening previous such bounds [2, 3, 6]. On the probabilistic side, we use the "reflection principle" and the FKG and related inequalities in order to study the problem on general trees.

UR - http://www.scopus.com/inward/record.url?scp=33748524852&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33748524852&partnerID=8YFLogxK

U2 - 10.1007/BF02773611

DO - 10.1007/BF02773611

M3 - Article

AN - SCOPUS:33748524852

SN - 0021-2172

VL - 154

SP - 299

EP - 336

JO - Israel Journal of Mathematics

JF - Israel Journal of Mathematics

ER -