Optimal low-degree hardness of maximum independent set

DOI10.4171/MSL/25MaRDI QIDQ2113266zbMATH OpenFDO

Authors Alexander S. Wein

Publication date 11 March 2022

Published in Mathematical Statistics and Learning (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2010.06563

zbMATH Keywords

random graphindependent setoverlap gap propertylow-degree polynomial

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Finding a Maximum Independent Set in a Sparse Random Graph
• Uncover Low Degree Vertices and Minimise the Mess: Independent Sets in Random Regular Graphs

Cites work

• scientific article; zbMATH DE number 3574966 (Why is no real title available?)
• scientific article; zbMATH DE number 7650426 (Why is no real title available?)
• A nearly tight sum-of-squares lower bound for the planted clique problem
• Algorithmic thresholds for tensor PCA
• Algorithms for heavy-tailed statistics: regression, covariance estimation, and beyond
• Following the Ground States of <scp>Full‐RSB</scp> Spherical Spin Glasses
• Large deviations of empirical neighborhood distribution in sparse random graphs
• Large independent sets in regular graphs of large girth
• Limits of local algorithms over sparse random graphs
• Limits of locally-globally convergent graph sequences
• Local algorithms for independent sets are half-optimal
• Non-Negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics
• On the independence number of random graphs
• Optimal low-degree hardness of maximum independent set
• Optimization of mean-field spin glasses
• State evolution for general approximate message passing algorithms, with applications to spatial coupling
• Suboptimality of local algorithms for a class of max-cut problems
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• The algorithmic hardness threshold for continuous random energy models
• The overlap gap property and approximate message passing algorithms for \(p\)-spin models
• Walksat Stalls Well Below Satisfiability

Cited in

(10)

• Optimal Low-Degree Hardness of Maximum Independent Set
• Computational lower bounds for graphon estimation via low-degree polynomials
• Average-case complexity of tensor decomposition for low-degree polynomials
• Algorithms approaching the threshold for semi-random planted clique
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics
• Optimizing mean field spin glasses with external field
• Optimal low-degree hardness of maximum independent set
• Tight Lipschitz hardness for optimizing mean field spin glasses
• scientific article; zbMATH DE number 1305522 (Why is no real title available?)
• Computational barriers to estimation from low-degree polynomials

This page was built for publication: Optimal low-degree hardness of maximum independent set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2113266)