Optimal low-degree hardness of maximum independent set
From MaRDI portal
Publication:2113266
DOI10.4171/MSL/25MaRDI QIDQ2113266
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
Related Items (4)
Computational barriers to estimation from low-degree polynomials ⋮ Optimizing mean field spin glasses with external field ⋮ Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics ⋮ Optimal low-degree hardness of maximum independent set
Cites Work
- Unnamed Item
- Unnamed Item
- Large deviations of empirical neighborhood distribution in sparse random graphs
- Algorithmic thresholds for tensor PCA
- On the independence number of random graphs
- Local algorithms for independent sets are half-optimal
- Optimization of mean-field spin glasses
- Optimal low-degree hardness of maximum independent set
- The algorithmic hardness threshold for continuous random energy models
- The overlap gap property and approximate message passing algorithms for \(p\)-spin models
- Large independent sets in regular graphs of large girth
- Suboptimality of local algorithms for a class of max-cut problems
- Limits of locally-globally convergent graph sequences
- Non-Negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics
- On independent sets in random graphs
- A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
- Following the Ground States of <scp>Full‐RSB</scp> Spherical Spin Glasses
- Algorithms for heavy-tailed statistics: regression, covariance estimation, and beyond
- State evolution for general approximate message passing algorithms, with applications to spatial coupling
- Walksat Stalls Well Below Satisfiability
- The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
- Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
- Limits of local algorithms over sparse random graphs
This page was built for publication: Optimal low-degree hardness of maximum independent set
