In this paper, assuming the low-degree conjecture, we provide evidence of computational hardness for two problems: (1) the (partial) matching recovery problem in the sparse correlated Erd\H{ o}s-R\'enyi graphs $\mathcal G(n,q;\rho)$ when the edge-density $q=n^{ -1+o(1)}$ and the correlation $\rho<\sqrt{ \alpha}$ lies below the Otter's threshold, this resolves a remaining problem in \cite{ DDL23+}; (2) the detection problem between a pair of correlated sparse stochastic block models $\mathcal S(n,\tfrac{ \lambda}{ n};k,\epsilon;s)$ and a pair of independent stochastic block models $\mathcal S(n,\tfrac{ \lambda s}{ n};k,\epsilon)$ when $\epsilon^2 \lambda s<1$ lies below the Kesten-Stigum (KS) threshold and $s<\sqrt{ \alpha}$ lies below the Otter's threshold, this resolves a remaining problem in \cite{ CDGL24+}. One of the main ingredient in our proof is to derive certain forms of \emph{ algorithmic contiguity} between two probability measures based on bounds on their low-degree advantage. To be more precise, consider the high-dimensional hypothesis testing problem between two probability measures $\mathbb{ P}$ and $\mathbb{ Q}$ based on the sample $\mathsf Y$. We show that if the low-degree advantage $\mathsf{ Adv}_{ \leq D} \big( \frac{ \mathrm{ d}\mathbb{ P}}{ \mathrm{ d}\mathbb{ Q}} \big)=O(1)$, then (assuming the low-degree conjecture) there is no efficient algorithm $\mathcal A$ such that $\mathbb{ Q}(\mathcal A(\mathsf Y)=0)=1-o(1)$ and $\mathbb{ P}(\mathcal A(\mathsf Y)=1)=\Omega(1)$. This framework provides a useful tool for performing reductions between different inference tasks, without requiring a strengthened version of the low-degree conjecture as in \cite{ MW23+, DHSS25+}.
Categories: stat.ML cs.DS cs.LG math.PR math.ST stat.TH