
## 3. Hardness at the KS threshold

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

#### Problem 3.1.

[Lenka Zdeborová] 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.