Locally Computable Hashing
Hash function families whose evaluation reads only a small, bounded number of key words, and the locality such families can achieve.
| Status | Problem | Tags |
|---|---|---|
|
Almost k-Wise Locality Gap Settled up to a \(\log n\) factor at word size 1 and at word size \(\Omega(\log^2 n)\) and above; the source gives no matching construction at all for intermediate word sizes, so the gap is recorded only where both a bound and a construction exist to compare. 4 open |
Limited IndependenceLocally Computable Hashingtight-boundadaptation (ai) |
No matching items