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 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.