### Skapa referens, olika format (klipp och klistra)

**Harvard**

Mossel, E., O'Donnell, R., Regev, O., Steif, J. och Sudakov, B. (2006) *Non-interactive correlation distillation, inhomogeneous Markovchains, and the reverse Bonami-Beckner inequality*.

** BibTeX **

@article{

Mossel2006,

author={Mossel, Elchanan and O'Donnell, Ryan and Regev, Oded and Steif, Jeffrey and Sudakov, Benny},

title={Non-interactive correlation distillation, inhomogeneous Markovchains, and the reverse Bonami-Beckner inequality},

journal={Israel Journal of Mathematics},

issn={0021-2172},

volume={154},

pages={299-336},

abstract={In this paper we study non-interactive correlation distillation (NICD), a generalization of
noise sensitivity previously studied earlier. 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:
(1). In the case of a $k$-leaf star graph (the model considered earlier by Mossel and O'Donnell),
we resolve the open question of whether the success probability must go to zero as $k \to \infty$.
We show that this is indeed the case and provide matching upper and lower bounds on the
asymptotically optimal rate (a slowly-decaying polynomial).
(2). 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.
(3). 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 very little-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. On the probabilistic side, we use
the ``reflection principle'' and the FKG and related inequalities in order to study the problem on
general trees. },

year={2006},

keywords={Markov chains, Bonami-Beckner inequality},

}

** RefWorks **

RT Journal Article

SR Electronic

ID 24583

A1 Mossel, Elchanan

A1 O'Donnell, Ryan

A1 Regev, Oded

A1 Steif, Jeffrey

A1 Sudakov, Benny

T1 Non-interactive correlation distillation, inhomogeneous Markovchains, and the reverse Bonami-Beckner inequality

YR 2006

JF Israel Journal of Mathematics

SN 0021-2172

VO 154

SP 299

OP 336

AB In this paper we study non-interactive correlation distillation (NICD), a generalization of
noise sensitivity previously studied earlier. 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:
(1). In the case of a $k$-leaf star graph (the model considered earlier by Mossel and O'Donnell),
we resolve the open question of whether the success probability must go to zero as $k \to \infty$.
We show that this is indeed the case and provide matching upper and lower bounds on the
asymptotically optimal rate (a slowly-decaying polynomial).
(2). 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.
(3). 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 very little-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. On the probabilistic side, we use
the ``reflection principle'' and the FKG and related inequalities in order to study the problem on
general trees.

LA eng

DO 10.1007/BF02773611

LK http://dx.doi.org/10.1007/BF02773611

OL 30