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

3. Hardness at the KS threshold

    1. In what sense is the “hard” regime hard?

      Problem 3.1.

      [Lenka Zdeborová] Can we formalize in what sense we believe that conjectured “hard” regions are hard? There are some caveats here because, for instance, statistical physics and the sum-of-squares hierarchy both predict a hard phase for XOR-SAT even though it can be solved efficiently by Gaussian elimination. However, Gaussian elimination fails in the presense of noise, so perhaps we have captured a “robust” notion of hardness.
        • Refuting colorability with SoS

          Problem 3.2.

          [Cris Moore] Can constant-degree sum-of-squares refute $k$-colorability for random graphs of average degree less than $k^2$ (i.e. below the Kesten-Stigum bound)?
            • Bounding independent set size with SoS

              Problem 3.3.

              [Luca Trevisan] For a random graph of average degree $d$, what upper bound can constant-degree sum-of-squares prove on the size of an independent set. It is conjectured that the answer is $C n/\sqrt{d}$ (for some constant $C$) even though the true size of the largest independent set is $\frac{n}{d} \log d$.
                • Failure of BP

                  Problem 3.4.

                  [Cris Moore] Show that BP fails on the SBM below the KS bound.
                    • Failure of MC

                      Problem 3.5.

                      [Cris Moore] Show that Monte-Carlo fails on the SBM below the KS bound. This is related to the quantity $Z(\alpha) = \sum_{\tau : \alpha(\sigma,\tau) \approx \alpha} P(G | \tau)$. We want to understand $\mathbb{E}_{G | \sigma} \log Z(\alpha)$. Here $\sigma$ and $\tau$ are colorings of the vertices and $\alpha$ is the overlap matrix $$\alpha_{rs} = \frac{|\sigma^{-1}(r) \cap \tau^{-1}(s)|}{n/k}.$$ It is tractible to compute the annealed average $\mathbb{E}_{G | \sigma} Z(\alpha)$. Is this quantity related?

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