Polynomial-time algorithms beating the overlap-gap threshold for independent sets

55

No. 471 in all physics · No. 8 in Statistical and Nonlinear Physics

Expert version

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.

How results are checked

See also

Comments (0)

Comments are not records: they are not signed, stamped or logged. How comments work

No comments yet.

Sign in to comment.

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.

History