We study the algorithmic task of finding a large independent set in a sparse Erdős– Rényi random graph with vertices and average degree . The maximum independent set is known to have size in the double limit followed by , but the best known polynomial-time algorithms can only find an independent set of half-optimal size . 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.
Cite this article
Alexander S. Wein, Optimal low-degree hardness of maximum independent set. Math. Stat. Learn. 4 (2021), no. 3/4, pp. 221–251DOI 10.4171/MSL/25