Optimal low-degree hardness of maximum independent set (Q2113266)

Summary: 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 \textit{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 \textit{local algorithms}.