Tree reconstruction conjecture for the two-state broadcast process with revealed nodes
Tree reconstruction conjecture for the two-state broadcast process with revealed nodes
Let be an infinite tree with root . In the two-state broadcast process, each vertex label is generated by assigning the root a uniformly random label, then propagating labels along each edge while retaining the parent label with probability and flipping it with probability . Independently, each vertex is included in a revealed set with probability , and let be the leaves at depth . Tree reconstruction conjecture. For every and ,
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.