Low-Degree Hardness of Detection for Correlated Erdős-Rényi Graphs
Jian Ding, Hang Du, Zhangsong Li
给定两个具有n顶点的Erdős-Rényi图,其边缘通过潜在的顶点对应相关联,我们研究低度多项式算法类相关相关性检测问题的复杂性下界。 我们提供证据表明,任何度-O(ρ^-1)多项式算法都未能用于检测,其中ρ是边缘相关性。 此外,在边缘密度 q=n^-1+o(1) 的稀疏方案中,我们提供证据表明任何度-d多项式算法都失效用于检测,只要日志 d=o( log n/log nq∯(log nq√(log n)) 和相关 ρ<√(α) 其中 α≈ 0.338 是 Otter 常数。 我们的结果表明,关于相关性检测和精确匹配恢复的几种最先进的算法可能基本上是最好的。
Given two Erdős-Rényi graphs with n vertices whose edges are correlated through a latent vertex correspondence, we study complexity lower bounds for the associated correlation detection problem for the class of low-degree polynomial algorithms. We provide evidence that any degree-O(ρ^-1) polynomial algorithm fails for detection, where ρ is the edge correlation. Furthermore, in the sparse regime where the edge density q=n^-1+o(1), we provide evidence that any degree-d polynomial algorithm fails f...