Bounded Independence for $k$-Min-Wise Hashing: Tight Bounds and Limitations of Structured Hashing

Abstract

Min-wise hashing and its $k$-min-wise extension are fundamental tools in sampling, sketching, similarity estimation, etc. A standard approach to constructing such families is bounded independence. For ordinary min-wise hashing, the required degree of independence is fully understood: $\Theta (\log 1/\delta )$-wise independence is both sufficient and necessary. For $k$-min-wise hashing, however, the best previous result only showed that $O(k\log \log 1/\delta +\log 1/\delta )$-wise independence suffices, with no matching lower bound. We give a tight characterization of the amount of bounded independence required for $k$-min-wise hashing, proving that $\Theta (k+\log 1/\delta )$-wise independence is both sufficient and necessary. This improves the previous upper bound and provides a matching lower bound. Consequently, the standard construction of bounded-independent hash families has seed length $O((k+\log 1/\delta )\cdot \log (N/\delta ))$. In particular, for polynomially small $\delta$ and any $\Omega (\log N)\le k\le N^{1-c}$, it achieves the optimal seed length $O(k\log N)$. We further investigate two standard low-independence hash families. For random affine functions over ${\mathbb{F}}_2$, which form a pairwise independent family, we show that the multiplicative error is $\Omega (\log N)$ even for ordinary min-wise hashing. For simple tabulation hashing, which is $3$-wise independent and performs well for ordinary min-wise hashing, we show that it incurs a multiplicative error $\Omega (N)$ for $k$-min-wise hashing whenever $k\ge 4$.

This paper merges and extends two concurrent and independent preprints: arXiv:2607.27157v1 and arXiv:2607.10255v2