Tree reconstruction conjecture for the two-state broadcast process with revealed nodes

Let TT be an infinite tree with root ρ\rho. In the two-state broadcast process, each vertex label τv{±1}\tau_v\in\{\pm 1\} is generated by assigning the root a uniformly random label, then propagating labels along each edge while retaining the parent label with probability 1η1-\eta and flipping it with probability η\eta. Independently, each vertex is included in a revealed set RR with probability pp, and let Tr\partial T_r be the leaves at depth rr. Tree reconstruction 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.

This conjecture would imply the claimed local optimality for the labeled two-cluster model through the tree coupling. The source reports simulations supporting it, but gives no proof; the problem remains open.

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).

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.