Optimal Low-Degree Hardness of Maximum Independent Set

2020/10/13 by Wein, Alexander S. · 6 citations
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Probability (math.PR)

paper · doi:10.48550/arxiv.2010.06563

Abstract

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 → ∞ 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ág, which proved the analogous result for the weaker class of local algorithms.

Cited by

• Independent sets and colorings of K_t,t,t-free graphs
• Binary perceptron computational gap -- a parametric fl RDT view
• A New Quantum Linear System Algorithm Beyond the Condition Number and Its Application to Solving Multivariate Polynomial Systems
• Are Neural Networks Collision Resistant?
• A Smooth Computational Transition in Tensor PCA
• Sharp Online Hardness for Large Balanced Independent Sets

Related

• The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
• Optimal Hardness of Online Algorithms for Large Independent Sets
• Asymptotic optimality of degree-greedy discovering of independent sets\n in Configuration Model graphs
• Large independent sets on random d-regular graphs with fixed degree d
• Independent sets in graphs with given minimum degree