Decelle–Krzakala–Moore–Zdeborová parameter-estimation threshold conjecture

From papers

Let G(n,a/n,b/n)\mathcal{G}(n,a/n,b/n) be the sparse planted partition model with two equal-sized clusters and parameters a>b>0a>b>0. A consistent estimator of aa and bb is an estimator whose estimates converge to the true parameters as nn\to\infty. Decelle–Krzakala–Moore–Zdeborová's parameter-estimation conjecture. If

(ab)2>2(a+b),(a-b)^2>2(a+b),

then there is a consistent estimator for aa and bb under G(n,a/n,b/n)\mathcal{G}(n,a/n,b/n); conversely, if

(ab)2<2(a+b),(a-b)^2<2(a+b),

then there is no consistent estimator. This predicts that parameter estimation has the same phase transition as community recovery in the sparse two-block model. The source presents the claim as a conjectural extension of statistical work on parameter estimation and gives no proof of either direction.

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

Elchanan Mossel, Joe Neeman and Allan Sly, “Stochastic Block Models and Reconstruction”, arXiv:1202.1499 (2012).

Solutions 0

No solutions have been posted yet.