Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs

Abstract

In this paper, assuming a natural strengthening of the low-degree conjecture, we provide evidence of computational hardness for two problems: (1) the (partial) matching recovery problem in the sparse correlated Erdos-R\'enyi graphs G(n,q;) when the edge-density q=n^-1+o(1) and the correlation < lies below the Otter's threshold, solving a remaining problem in DDL23+; (2) the detection problem between the correlated sparse stochastic block model S(n,n;k,;s) and a pair of independent stochastic block models S(n, sn;k,) when ^2 s<1 lies below the Kesten-Stigum (KS) threshold and s< lies below the Otter's threshold, solving a remaining problem in CDGL24+. 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 P and Q based on the sample Y. We show that if the low-degree advantage Adv_ D ( dPdQ )=O(1), then (assuming the low-degree conjecture) there is no efficient algorithm A such that Q( A( Y)=0)=1-o(1) and P( A( Y)=1)=(1). This framework provides a useful tool for performing reductions between different inference tasks.

Tasks

Reproductions