Locality Preserving Hashing
Hashing a long string to a position so robustly that shifting the input moves the output by exactly the shift, using a sublinear number of queries.
| Status | Problem | Tags |
|---|---|---|
|
Optimal 2D LPHS Open, and asserted rather than asked: the source prints the algorithm, conjectures the error rate, reports experiments consistent with it, states it could not analyse it, and leaves settling it to future work. The matching lower bound is the source’s own theorem, so a proof would close the two-dimensional case exactly. 7 open |
Distributed Discrete LogarithmGeneric Group ModelLocality Preserving Hashingtight-boundadaptation (ai) | |
|
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