Closing the Logarithmic Locality Gap for Almost k-Wise Independent Hashing
Statement: AI-written, not yet formalized. Proof: open – no attempt yet.
A local hash function reads only a small number of words of its own key on any one evaluation. Almost \(k\)-wise independent hashing lets that number shrink far below what perfect \(k\)-wise independence needs, and the source pins down, for input/output size \(n\) and error \(2^{-n}\), an unconditional lower bound on how small the locality can be, matched by an explicit construction up to a factor of \(\log n\) — but only at word size \(1\) and at word size at least about \((\log n)^{2}\). For every word size strictly in between, it gives no matching construction at all.
View PDF · LaTeX source · Formal statement — not yet formalized
The object (the source’s setting). A family \(\mathcal{F} = \{f_{s} : \{0,1\}^{n} \to \{0,1\}^{n}\}_{s \in \Sigma^{\ell}}\), keyed by a seed \(s\) from a word alphabet \(\Sigma = \{0,1\}^{w}\), is \(t\)-word-local if evaluating \(f_{s}(x)\) reads at most \(t\) of the \(\ell\) words of \(s\), and is \(\varepsilon\)-almost \(k\)-wise independent if no distinguisher making at most \(k\) oracle queries can tell \(f_{s}\) apart from a uniformly random function with advantage more than \(\varepsilon\).
What is proved (the source’s Theorem 5.1, specialized to \(n = m\), \(\varepsilon = 2^{-n}\), \(k = \mathrm{poly}(n)\)). Every such family has locality \(t \ge \Omega(n/(\sqrt w \log n))\), for every word size \(w\). Matching explicit constructions, achieving \(t = O(n/\sqrt w)\), are given only at \(w = 1\) (Theorem 5.7) and at \(w = \Omega(\log^{2}k + \log^{2}n)\) up to \(w \le n^{2}\) (Theorem 5.10) — the source’s own results summary states the latter needs a “sufficiently large word size.” For \(2 \le w = o(\log^{2}n)\), no construction matching the lower bound is given at all.
Conjecture. For a word size \(w \in \{1\} \cup [\Omega(\log^{2}n), n^{2}]\) — the range where the source gives both a lower bound and a matching construction — determine the true order of the minimal locality, by either exhibiting an explicit family with \(t = o(n/\sqrt w)\) (improving the construction), or proving every such family must have \(t = \Omega(n/\sqrt w)\) (improving the lower bound), for at least one such \(w\).
How the source states it. Its closing section (page 20) reads: “Another open problem is to close the logarithmic gaps between the lower bounds and explicit constructions of almost-independent hashing when the input and output size is \(n\) and the error is \(\varepsilon = 2^{-n}\).”
Where this statement is silent. For \(2 \le w = o(\log^{2}n)\) the source establishes no \(O(n/\sqrt w)\)-locality construction at all, so there is no known upper bound in that range for a log-factor gap to be measured against. That intermediate range is instead the subject of the source’s separate remark about unifying its bit-local and word-local constructions into one spanning every word size — a different, easier-stated question about the elegance of the construction, not about the locality value itself.
Sources
- Dodis, Lovett and Wichs. Locally Computable High Independence Hashing. IACR ePrint 2026/622. The source. The lower bound is Theorem 5.1; the constructions are Theorem 5.7 (\(w=1\)) and Theorem 5.10 (\(w = \Omega(\log^{2}k+\log^{2}n)\)); the open problem is Section 6 (“Summary and Open Problems”), page 20.
- Siegel. On Universal Classes of Fast High Performance Hash Function, Their Time-Space Tradeoff, and Their Applications. FOCS 1989. Initiates the line on locally computable independent hashing the source continues.
- Siegel. On Universal Classes of Extremely Random Constant-Time Hash Functions. SIAM J. Comput. 33(3):505–543, 2004.
- Larsen, Pagh, Persiano, Pitassi, Yeo and Zamir. Optimal Non-Adaptive Cell Probe Dictionaries and Hashing. ICALP 2024, LIPIcs vol. 297. A later advance in the same line, cited by the source.
View PDF — no proof written yet · LaTeX source — no proof written yet · Formal proof — not yet formalized
Open. The source’s own techniques are the visible route in both directions.
Toward a better construction. Theorem 5.10’s construction combines a word-based overlap-avoiding hash family with a robust matrix, via a case split on how \(w\) compares to \(k^{2}\) and \(n^{2}\); removing the \(\log n\) factor would mean sharpening that combination, or replacing it with a different overlap-avoiding family, without weakening the achieved independence or error.
Toward a better lower bound. Theorem 5.1’s argument is a lazy-sampling/counting distinguisher: it partitions inputs by which \(t\) words of the key they read, and bounds how many query outputs are consistent with any fixed key. Sharpening that same counting argument, in the regime where a matching construction is already known, is the natural route to removing the log factor from the other side.
Checked against the literature, 2026-08-24. No proof, refutation or improvement found in the months since the ePrint. This is a targeted check on a very recent paper, not an exhaustive sweep.
What this conjecture is not. It is not the source’s separate remark about unifying the bit-local and word-local constructions into one that spans every word size \(1 \le w \le n^{2}\) — that is a question about the elegance of exposition (the two known constructions already give near-optimal parameters across their own ranges), not about narrowing the gap between a lower bound and an achieved locality. It is recorded on the hub as a distinct item.
What a reviewer should be suspicious of, in order. First, that Theorem 5.10’s standing hypothesis \(w = \Omega(\log^{2}k + \log^{2}n)\) really is required throughout its proof’s case split, and not just in one sub-case. Second, that Theorem 5.1’s specialization to \(k = \mathrm{poly}(n)\) implicitly needs \(k > tw/n + 1\), which should be checked to hold across the whole word-size range this statement covers.
Attackability for an AI proof harness (conjecture-triage, 2026-08-25). Scored 28/31, verdict GO, difficulty band “routine” — this rates how tractable a bounded multi-agent campaign would find it, not the statement’s intrinsic mathematical difficulty. The source’s own perfect-independence case is an exactly-settled sibling with no log-gap, giving a crisp generalization hypothesis; the gap itself is a single log factor from one paper’s own counting argument and construction; and it is a genuinely finite, exactly-checkable combinatorial statement with no idealized-model ambiguity at all. Recommended configuration: full campaign, Case Planner laddering from the perfect-independence base case, Prover and Refuter in parallel on both directions. Full record: latex/conjectures/almost-kwise-locality-log-gap/triage.json.