3. Hardness at the KS threshold

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 sumofsquares hierarchy both predict a hard phase for XORSAT 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 constantdegree sumofsquares refute $k$colorability for random graphs of average degree less than $k^2$ (i.e. below the KestenStigum bound)? 
Bounding independent set size with SoS
Problem 3.3.
[Luca Trevisan] For a random graph of average degree $d$, what upper bound can constantdegree sumofsquares 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 MonteCarlo 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.