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 | Statement | 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