Broadcasting-with-revealed-nodes boundary irrelevance conjecture

From papers

Let TT be an infinite tree with root ρ\rho. Assign the root a uniformly random label in {±1}\{\pm1\} and propagate labels along edges, retaining the parent label with probability 1η1-\eta and flipping it with probability η\eta. Let (T,τ)(T,\tau) be the resulting labeled tree. Independently include each node in RR with probability pp, and let Tr\partial T_r be the leaves at depth rr. Boundary irrelevance conjecture. For every p>0p>0 and η<1/2\eta<1/2,

limrEPr[τρ=1τR]Pr[τρ=1τR,τTr]=0.\lim_{r\to\infty}\mathbb{E}\left|\Pr[\tau_\rho=1\mid\tau_R]-\Pr[\tau_\rho=1\mid\tau_R,\tau_{\partial T_r}]\right|=0.

The source identifies this as the tree-information-flow conjecture underlying the local-recovery claim and reports simulations supporting it. It remains open in the supplied text.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Varun Kanade, Elchanan Mossel and Tselil Schramm, “Global and Local Information in Clustering Labeled Block Models”, arXiv:1404.6325 (2014).

Solutions 0

No solutions have been posted yet.