| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

4. Provable algorithms at the KS threshold

    1. Analyze BP


      Add remark

      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


          Add remark

          Problem 4.2.

          [Lenka Zdeborová] 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


              Add remark

              Problem 4.3.

              [Lenka Zdeborová] 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.