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