← All problems

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

14 years old · traced to

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 n→∞n\to\infty. Decelle–Krzakala–Moore–Zdeborová's parameter-estimation conjecture. If

(a−b)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

(a−b)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.

References

Status

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

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.