Broadcasting information conjecture for regular and Poisson Galton–Watson trees

Let TT be a regular tree or a Galton-Watson tree with Poisson offspring distribution, with root vertex ρ\rho. Let (T,ρ,θ,W)(T,\rho,\theta,W) denote the corresponding broadcast model with parameter 0<θ<10<\theta<1 and survey channel WW, and let Pe(W)P_e(W) be the error probability of the survey channel. The property (BI) is the broadcasting-information property considered in the paper. Broadcasting information conjecture. Property (BI) holds for (T,ρ,θ,W)(T,\rho,\theta,W) for all 0<θ<10<\theta<1 and all WW such that Pe(W)12P_e(W)\ne\frac12. This would extend the sufficient conditions established earlier, including the high-signal regimes described in the preceding corollary, to every nontrivial survey channel. The parser supplies no evidence that this conjecture has been resolved.

Sources & referencesView supporting material

Primary source

Emmanuel Abbe, Elisabetta Cornacchia, Yuzhou Gu and Yury Polyanskiy, “Stochastic block model entropy and broadcasting on trees with survey”, arXiv:2101.12601 (2021).

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.