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