基于低度假设，证明两类相关图模型的推断难题，为计算下界提供新工具。
Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity
- 利用低度优势界定算法相容性，构建推断任务间归约框架。
- 在边密度 $q=n^{-1+o(1)}$ 时，部分匹配恢复问题难解。
- 适用于研究图模型统计推断的计算复杂性，尤其适合理论方向读者。
本文在低度猜想假设下，为两个问题提供计算硬性证据：(1) 当边密度 $q=n^{-1+o(1)}$ 且相关性 $ρ<\sqrtα$ 低于 Otter 阈值时，稀疏相关 Erdős-Rényi 图 $\mathcal G(n,q;ρ)$ 中的（部分）匹配恢复问题难以求解，解决了 \\cite{DDL23+} 中遗留的问题；(2) 当 $ε^2 λs<1$ 低于 Kesten-Stigum (KS) 阈值且 $s<\sqrtα$ 低于 Otter 阈值时，相关稀疏社区模型 $\mathcal S(n,\tfracλ{n};k,ε;s)$ 与独立社区模型 $\mathcal S(n,\tfrac{λs}{n};k,ε)$ 之间的检测问题也难以解决，解决了 \\cite{CDGL24+} 中的剩余问题。证明核心是基于低度优势边界，推导出两概率测度间的算法相容性形式。具体而言，考虑基于样本 $\mathsf Y$ 的高维假设检验 $\mathbb{P}$ 与 $\mathbb{Q}$，若低度优势 $\mathsf{Adv}_{\leq D} \big( \frac{\mathrm{d}\mathbb{P}}{\mathrm{d}\mathbb{Q}} \big)=O(1)$，则在低度猜想下，不存在高效算法 $\mathcal A$ 满足 $\mathbb{Q}(\mathcal A(\mathsf Y)=0)=1-o(1)$ 且 $\mathbb{P}(\mathcal A(\mathsf Y)=1)=Ω(1)$。该框架可直接用于不同推断任务间的归约，无需依赖 \\cite{MW23+, DHSS25+} 中所需的强化低度猜想。
原文摘要 · Abstract (English)
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ős-Rényi graphs $\mathcal G(n,q;ρ)$ when the edge-density $q=n^{-1+o(1)}$ and the correlation $ρ<\sqrtα$ 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λ{n};k,ε;s)$ and a pair of independent stochastic block models $\mathcal S(n,\tfrac{λs}{n};k,ε)$ when $ε^2 λs<1$ lies below the Kesten-Stigum (KS) threshold and $s<\sqrtα$ 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)=Ω(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+}.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。