Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity

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 ErdHos-R'enyi graphs mathcal G(n,q;ρ) when the edge-density q=n-1+o(1) and the correlation ρ<√α lies below the Otter's threshold, this resolves a remaining problem in citeDDL23+; (2) the detection problem between a pair of correlated sparse stochastic block models mathcal S(n,tfracλn;k,ε;s) and a pair of independent stochastic block models mathcal S(n,tfracλ sn;k,ε) when ε2 λ s<1 lies below the Kesten-Stigum (KS) threshold and s<√α lies below the Otter's threshold, this resolves a remaining problem in citeCDGL24+. One of the main ingredient in our proof is to derive certain forms of 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 mathbbP and mathbbQ based on the sample mathsf Y. We show that if the low-degree advantage mathsfAdv≤ D big( fracdmathbbPdmathbbQ big)=O(1), then (assuming the low-degree conjecture) there is no efficient algorithm mathcal A such that mathbbQ(mathcal A(mathsf Y)=0)=1-o(1) and mathbbP(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 citeMW23+, DHSS25+.