Polynomial-time algorithms beating the overlap-gap threshold for independent sets
55No. 471 in all physics · No. 8 in Statistical and Nonlinear Physics
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.
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).
No solutions, ideas or subproblems yet.
See also
- Related Does quantum annealing outscale classical algorithms on 3D spin glasses?
- Related A correct low-degree criterion for polynomial-time hardness of inference
Details, signature and history
- Kind
- Well-posed question
- Answer
- Yes no
- Topic review
- L. Zdeborova and F. Krzakala, Statistical physics of inference: thresholds and algorithms, Advances in Physics 65, 2016. Link
- Record
- Revision 1 · imported from the seed collection · compiled by AI, not yet reviewed by an editor
Proof
- Fingerprint
- c515d9c86237…
- Public log
- Entry 2,093, in checkpoint 2,123
- In the log by
- Block 969,698, 2026-10-03
This text was in the PubPhys log by that date. The date says nothing about when the problem was first posed.
Comments (0)
Comments are not records: they are not signed, stamped or logged. How comments work
No comments yet.
Sign in to comment.