Overlap Gap Property
The overlap gap property as a barrier to stable, online and local algorithms on random structures, and its use as evidence of average-case hardness.
| Status | Statement | Tags |
|---|---|---|
|
SBP Collision Resistance Posed as a displayed Open Question and called a central open challenge. The source gives an efficient online collision finder for small kappa and an overlap-gap-based online lower bound for a different, randomized activation – introduced precisely because the SBP’s own collision space resists a first-moment analysis. For very large kappa collisions become trivial. The middle window is reached by neither technique. 4 open |
Average Case HardnessCollision Resistant HashingOverlap Gap PropertyPlanted Constraint Satisfactionseparation | |
|
CHV Online Threshold Conjecture 1 of the source, its online threshold conjecture. The source gives an online algorithm achieving kappa = O(sqrt(alpha)/B) and an overlap-gap argument against stable algorithms; the conjecture pins the constant sqrt(pi/8) as the exact place where online algorithms stop. Separately it proves, under worst-case lattice hardness, that no polynomial-time algorithm solves CHV for kappa = O(1/(B n^(1/2+eps))). 4 open |
Average Case HardnessCollision Resistant HashingLocality Preserving HashingOverlap Gap Propertytight-bound |
No matching items