Broadcasting-with-revealed-nodes boundary irrelevance conjecture

About 12 years old · traced to

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,

lim⁡r→∞E∣Pr⁡[τρ=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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.