mlsanityData to 7 Oct 2026

Optimal Low-Degree Hardness of Maximum Independent Set

arXiv 2010.06563 ↗First posted 13 Oct 2020cs.CC cs.DS math.PRcited by 16

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 2; 2023: 4; 2024: 1; 2025: 5; 2026: 2.

16 papers.

Sort:

  1. 2022The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statisticscited by 31
  2. 2021The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomialscited by 14
  3. 2021Reconstruction on Trees and Low-Degree Polynomialscited by 10
  4. 2022Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomialscited by 6
  5. 2023Computational Lower Bounds for Graphon Estimation via Low-degree Polynomialscited by 6
  6. 2024A computational transition for detecting correlated stochastic block models by low-degree polynomialscited by 6
  7. 2025Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDTcited by 5
  8. 2023SQ Lower Bounds for Random Sparse Planted Vector Problemcited by 3
  9. 2025Binary perceptron computational gap -- a parametric fl RDT viewcited by 3
  10. 2025Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguitycited by 2
  11. 2023Barriers for the performance of graph neural networks (GNN) in discrete random structures. A comment on~citeschuetz2022combinatorial,citeangelini2023modern,citeschuetz2023replycited by 1
  12. 2026Parametric RDT approach to computational gap of symmetric binary perceptroncited by 1
4 more
  1. 2023On a Near-Optimal & Efficient Algorithm for the Sparse Pooled Data Problemcited by 0
  2. 2025A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomialscited by 0
  3. 2025A Smooth Computational Transition in Tensor PCAcited by 0
  4. 2026Ultrametric OGP - parametric RDT symmetric binary perceptron connectioncited by 0