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 | Problem | 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+\varepsilon}))\). 4 open |
Average Case HardnessCollision Resistant HashingLocality Preserving HashingOverlap Gap Propertytight-bound |
No matching items