
4. Provable algorithms at the KS threshold

1. Analyze BP

Problem 4.1.

[Elchanan Mossel] For the symmetric 2-groups SBM, show that BP (with random initialization) achieves $\varepsilon$ correlation with the truth, above the KS bound.
• BP with good initialization

Problem 4.2.

[Lenka Zdeborová] Run BP with a ‘good’ initialization (e.g. using a spectral method based on the non-backtracking walk matrix). Show that it achieves the optimal overlap with the truth.
• Analyze Gibbs sampling

Problem 4.3.

[Lenka Zdeborová] For the symmetric 2-groups SBM, show that Gibbs sampling achieves $\varepsilon$ correlation with the truth, above the KS bound.

Cite this as: AimPL: Connecting communities via the block model, available at http://aimpl.org/blockmodel.