论文标题
最大独立集的最佳低度硬度
Optimal Low-Degree Hardness of Maximum Independent Set
论文作者
论文摘要
我们研究了在稀疏的Erdős-rényi随机图中找到具有$ n $ VERTICES和平均度$ D $的大型独立套件的算法任务。已知最大独立集在双重限制$ n \ to \ infty $中具有尺寸$ $（2 \ log d / d）n $，其次是$ d \ to \ infty $，但是最著名的多项式算法只能找到一组独立的半典型大小$ $（\ log log d / d / d / d d / d）n $。我们表明，一类低度多项式算法可以找到半大小的独立集，但没有更大的算法，这取决于Gamarnik，Jagannath和作者的结果。这概括了Rahman和Virág的早期工作，这证明了局部算法较弱的类似结果。
We study the algorithmic task of finding a large independent set in a sparse Erdős-Rényi random graph with $n$ vertices and average degree $d$. The maximum independent set is known to have size $(2 \log d / d)n$ in the double limit $n \to \infty$ followed by $d \to \infty$, but the best known polynomial-time algorithms can only find an independent set of half-optimal size $(\log d / d)n$. We show that the class of low-degree polynomial algorithms can find independent sets of half-optimal size but no larger, improving upon a result of Gamarnik, Jagannath, and the author. This generalizes earlier work by Rahman and Virág, which proved the analogous result for the weaker class of local algorithms.
