# Optimal Low-Degree Hardness of Maximum Independent Set

arXiv: https://arxiv.org/abs/2010.06563 · HTML: https://mlsanity.com/paper/2010.06563/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Oct 2020.

## Built on by (most cited first, 16 of 16)

- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials](https://mlsanity.com/paper/2106.02129/) (2021)
- [Reconstruction on Trees and Low-Degree Polynomials](https://mlsanity.com/paper/2109.06915/) (2021)
- [Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials](https://mlsanity.com/paper/2211.05274/) (2022)
- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [A computational transition for detecting correlated stochastic block models by low-degree polynomials](https://mlsanity.com/paper/2409.00966/) (2024)
- [Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT](https://mlsanity.com/paper/2506.19276/) (2025)
- [SQ Lower Bounds for Random Sparse Planted Vector Problem](https://mlsanity.com/paper/2301.11124/) (2023)
- [Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity](https://mlsanity.com/paper/2502.09832/) (2025)
- [Binary perceptron computational gap -- a parametric fl RDT view](https://mlsanity.com/paper/2511.01037/) (2025)
- [Barriers for the performance of graph neural networks (GNN) in discrete random structures. A comment on~citeschuetz2022combinatorial,citeangelini2023modern,citeschuetz2023reply](https://mlsanity.com/paper/2306.02555/) (2023)
- [Parametric RDT approach to computational gap of symmetric binary perceptron](https://mlsanity.com/paper/2601.10628/) (2026)
- [On a Near-Optimal & Efficient Algorithm for the Sparse Pooled Data Problem](https://mlsanity.com/paper/2312.14588/) (2023)
- [A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomials](https://mlsanity.com/paper/2504.03097/) (2025)
- [A Smooth Computational Transition in Tensor PCA](https://mlsanity.com/paper/2509.09904/) (2025)
- [Ultrametric OGP - parametric RDT symmetric binary perceptron connection](https://mlsanity.com/paper/2604.19712/) (2026)

## Abstract (arXiv)

We study the algorithmic task of finding a large independent set in a sparse ErdHos-R'enyi 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 → ∞ followed by d → ∞, 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'ag, which proved the analogous result for the weaker class of local algorithms.