On the public citation graph

Optimal low-degree hardness of maximum independent set

0 signed · 72 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1002/rsa.20550openalex-snapshot
On independent sets in random graphs
inferredcites →https://doi.org/10.1007/978-3-030-97127-4_1openalex-snapshot
Notes on Computational Hardness of Hypothesis Testing: Predictions Using the Low-Degree Likelihood Ratio
inferredcites →https://doi.org/10.1007/s00039-014-0258-7openalex-snapshot
Limits of locally–globally convergent graph sequences
inferredcites →https://doi.org/10.1007/s00440-014-0590-8openalex-snapshot
Large deviations of empirical neighborhood distribution in sparse random graphs
inferredcites →https://doi.org/10.1007/s10208-022-09568-6openalex-snapshot
Detection Thresholds in Very Sparse Matrix Completion
inferredcites →https://doi.org/10.1007/s10208-023-09603-0openalex-snapshot
Subexponential-Time Algorithms for Sparse PCA
inferredcites →https://doi.org/10.1007/s10955-022-02976-6openalex-snapshot
Algorithmic Pure States for the Negative Spherical Perceptron
inferredcites →https://doi.org/10.1016/0012-365x(90)90149-copenalex-snapshot
On the independence number of random graphs
inferredcites →https://doi.org/10.1016/j.jctb.2007.02.006openalex-snapshot
Large independent sets in regular graphs of large girth
inferredcites →https://doi.org/10.1017/cbo9780511813603openalex-snapshot
Probability and Computing
inferredcites →https://doi.org/10.1073/pnas.0909892106openalex-snapshot
Message-passing algorithms for compressed sensing
inferredcites →https://doi.org/10.1093/imaiai/iat004openalex-snapshot
State evolution for general approximate message passing algorithms, with applications to spatial coupling
inferredcites →https://doi.org/10.1109/focs.2016.53openalex-snapshot
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
inferredcites →https://doi.org/10.1109/focs.2017.42openalex-snapshot
Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems
inferredcites →https://doi.org/10.1109/focs.2017.72openalex-snapshot
The Power of Sum-of-Squares for Detecting Hidden Structures
inferredcites →https://doi.org/10.1109/focs.2019.00087openalex-snapshot
Optimization of the Sherrington-Kirkpatrick Hamiltonian
inferredcites →https://doi.org/10.1109/focs46700.2020.00021openalex-snapshot
Low-Degree Hardness of Random Optimization Problems
inferredcites →https://doi.org/10.1109/tit.2015.2457942openalex-snapshot
Non-Negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics
inferredcites →https://doi.org/10.1145/1806689.1806706openalex-snapshot
Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
inferredcites →https://doi.org/10.1145/3357713.3384329openalex-snapshot
Algorithms for heavy-tailed statistics: regression, covariance estimation, and beyond
inferredcites →https://doi.org/10.1214/16-aop1094openalex-snapshot
Local algorithms for independent sets are half-optimal
inferredcites →https://doi.org/10.1214/16-aop1114openalex-snapshot
Limits of local algorithms over sparse random graphs
inferredcites →https://doi.org/10.1214/18-aop1291openalex-snapshot
Suboptimality of local algorithms for a class of max-cut problems
inferredcites →https://doi.org/10.1214/19-aop1415openalex-snapshot
Algorithmic thresholds for tensor PCA
inferredcites →https://doi.org/10.1214/20-aop1448openalex-snapshot
The overlap gap property and approximate message passing algorithms for $p$-spin models
inferredcites →https://doi.org/10.1214/21-aop1519openalex-snapshot
Optimization of mean-field spin glasses
inferredcites →https://doi.org/10.1214/21-aos2123openalex-snapshot
Tensor clustering with planted structures: Statistical optimality and computational limits
inferredcites →https://doi.org/10.1214/22-aos2179openalex-snapshot
Computational barriers to estimation from low-degree polynomials
inferredcites →https://doi.org/10.4230/lipics.itcs.2020.78openalex-snapshot
Computational Hardness of Certifying Bounds on Constrained PCA Problems
inferredcites →https://doi.org/10.4230/lipics.itcs.2021.75openalex-snapshot
Computational Hardness of Certifying Bounds on Constrained PCA Problems
inferredcites →https://doi.org/10.48550/arxiv.1402.0052openalex-snapshot
Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem
inferredcites →https://doi.org/10.48550/arxiv.1411.1076openalex-snapshot
A statistical model for tensor PCA
inferredcites →https://doi.org/10.48550/arxiv.1507.03269openalex-snapshot
Tensor principal component analysis via sum-of-squares proofs
inferredcites →https://doi.org/10.48550/arxiv.1812.04588openalex-snapshot
Following the ground-states of full-RSB spherical spin glasses
inferredcites →https://doi.org/10.48550/arxiv.2005.08099openalex-snapshot
Reducibility and Statistical-Computational Gaps from Secret Leakage
inferredcites →https://doi.org/10.48550/arxiv.2008.12237openalex-snapshot
Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
inferredcites →https://doi.org/10.48550/arxiv.2009.06107openalex-snapshot
Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1002/cpa.22222openalex-snapshot
Tight Lipschitz hardness for optimizing mean field spin glasses
inferred← citeshttps://doi.org/10.1007/s00440-025-01370-zopenalex-snapshot
The algorithmic phase transition of random graph alignment problem
inferred← citeshttps://doi.org/10.1007/s00440-025-01414-4openalex-snapshot
Shattering in the Ising p-spin glass model
inferred← citeshttps://doi.org/10.1016/j.jestch.2025.101995openalex-snapshot
A greedy approach to solve maximum independent set problem: Differential Malatya independent set algorithm
inferred← citeshttps://doi.org/10.1016/j.trc.2025.105312openalex-snapshot
Solving the Integrated-tasks satellite range scheduling problem: A surrogate-assisted variable neighborhood search approach
inferred← citeshttps://doi.org/10.1073/pnas.2108492118openalex-snapshot
The overlap gap property: A topological barrier to optimizing over random structures
inferred← citeshttps://doi.org/10.1073/pnas.2314092120openalex-snapshot
Barriers for the performance of graph neural networks (GNN) in discrete random structures
inferred← citeshttps://doi.org/10.1088/1742-5468/ac9cc8openalex-snapshot
Disordered systems insights on computational hardness
inferred← citeshttps://doi.org/10.1088/1742-5468/ae23beopenalex-snapshot
Overlap gap and computational thresholds in the square wave perceptron
inferred← citeshttps://doi.org/10.1088/1742-5468/ae4f7fopenalex-snapshot
Binary perceptron computational gap: a parametric fl-RDT view
inferred← citeshttps://doi.org/10.1103/6shh-9h5mopenalex-snapshot
Are Neural Networks Collision Resistant?
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00038openalex-snapshot
The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials
inferred← citeshttps://doi.org/10.1109/focs54457.2022.00037openalex-snapshot
Tight Lipschitz Hardness for optimizing Mean Field Spin Glasses
inferred← citeshttps://doi.org/10.1109/focs54457.2022.00038openalex-snapshot
Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization
inferred← citeshttps://doi.org/10.1109/tit.2026.3659093openalex-snapshot
A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomials
inferred← citeshttps://doi.org/10.1137/1.9781611977073.49openalex-snapshot
Algorithmic Thresholds for Refuting Random Polynomial Systems
inferred← citeshttps://doi.org/10.1137/1.9781611977912.54openalex-snapshot
Gap Amplification for Reconfiguration Problems
inferred← citeshttps://doi.org/10.1137/22m150263xopenalex-snapshot
Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics
inferred← citeshttps://doi.org/10.1137/24m1701575openalex-snapshot
The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
inferred← citeshttps://doi.org/10.1137/25m1790531openalex-snapshot
Sharp Phase Transitions for the Overlap Gap Property
inferred← citeshttps://doi.org/10.1145/3564246.3585232openalex-snapshot
Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials
inferred← citeshttps://doi.org/10.1145/3779053openalex-snapshot
Gap Amplification for Reconfiguration Problems
inferred← citeshttps://doi.org/10.1214/22-aos2179openalex-snapshot
Computational barriers to estimation from low-degree polynomials
inferred← citeshttps://doi.org/10.1214/23-aap1953openalex-snapshot
Algorithmic obstructions in the random number partitioning problem
inferred← citeshttps://doi.org/10.1214/23-ejp1066openalex-snapshot
Optimizing mean field spin glasses with external field
inferred← citeshttps://doi.org/10.1214/24-aos2437openalex-snapshot
Computational lower bounds for graphon estimation via low-degree polynomials
inferred← citeshttps://doi.org/10.1214/24-aos2484openalex-snapshot
Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing
inferred← citeshttps://doi.org/10.1214/25-aos2517openalex-snapshot
Low-degree hardness of detection for correlated Erdős–Rényi graphs
inferred← citeshttps://doi.org/10.1214/25-aos2565openalex-snapshot
A computational transition for detecting correlated stochastic block models by low-degree polynomials
inferred← citeshttps://doi.org/10.2140/pmp.2025.6.961openalex-snapshot
Sampling from mean-field Gibbs measures via diffusion processes
inferred← citeshttps://doi.org/10.3150/24-bej1784openalex-snapshot
On a near-optimal and efficient algorithm for the sparse pooled data problem
inferred← citeshttps://doi.org/10.3390/computation11100206openalex-snapshot
Large Independent Sets on Random d-Regular Graphs with Fixed Degree d
inferred← citeshttps://doi.org/10.48550/arxiv.2011.03693openalex-snapshot
Hypothesis testing with low-degree polynomials in the Morris class of exponential families
inferred← citeshttps://doi.org/10.48550/arxiv.2110.07847openalex-snapshot
Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses
inferred← citeshttps://doi.org/10.52202/068431-1376openalex-snapshot
Reconstruction on Trees and Low-Degree Polynomials
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.