Polynomial-time algorithms beating the overlap-gap threshold for independent sets
In plain words
In a large random network, simple fast algorithms find a set of unconnected nodes only half as large as the largest one that exists. The overlap gap property (good solutions form separated clusters with no intermediate overlaps) blocks many algorithms, and the question is whether every fast algorithm is blocked.
Precise statement
In the Erdos-Renyi graph $G(n, d/n)$ with large fixed average degree $d$, the largest independent set has size about $2 (\ln d / d)n$, while greedy and known polynomial-time algorithms reach about $(\ln d / d)n$. Does any polynomial-time algorithm output, with high probability, an independent set of size $(1 + \epsilon)(\ln d / d)n$ for a fixed $\epsilon > 0$ and all sufficiently large $d$? The answer is yes (an algorithm with proof) or no (a proof of hardness for all polynomial-time algorithms under a stated assumption).
What would settle it
An explicit polynomial-time algorithm with a proven guarantee above (ln d / d) n, or a reduction proving hardness from a standard complexity assumption.
Status in the literature
Unverified note: it names recent work and was partly written without a live literature search; it awaits a check by an editor.
The overlap gap property rules out local algorithms (Gamarnik and Sudan 2014; Rahman and Virag 2017) and low-degree polynomial algorithms (Wein 2022); no result covers general polynomial-time algorithms (2026).
Results
No results have been posted on this problem yet.
Post a result · how results are checked
Sign in to follow or save this problem
Comments (0)
Comments are not records: they are not signed, stamped or logged. How comments work
No comments yet.
Sign in to comment.