Explicit Min-wise Hash Families with Optimal Size

We study explicit constructions of min-wise hash families and their extension to k-min-wise hash families. Informally, a min-wise hash family guarantees that for any fixed subset X ⊆ [N ], every element in X has an equal chance to have the smallest value among all elements in X; a k-min-wise hash family guarantees this for every subset of size k in X. Min-wise hash is widely used in many areas of computer science such as sketching [Coh16], web page detection [Hen06], and ℓ 0 sampling [CF14]. For applications like similarity estimation [CDF + 01] and rarity estimation [DM02], the space complexity of their streaming algorithms is roughly equal to the number of random bits used to construct such families.

The classical works by Indyk [Ind01] and Pătraşcu and Thorup [PT16] have shown Θ(log(1/δ))wise independent families give min-wise hash of multiplicative (relative) error δ, resulting in a construction with Θ(log(1/δ) log N ) random bits. While this is optimal for constant errors, it leaves a gap to the existential bound of O(log(N/δ)) bits whenever δ is sub-constant, which is needed in several applications. Based on a reduction from pseudorandom generators for combinatorial rectangles by Saks, Srinivasan, Zhou and Zuckerman [SSZZ00], Gopalan and Yehudayoff [GY20] improved the number of bits to O(log N log log N ) for polynomially small errors δ. However, no construction with O(log N ) bits (polynomial size family) and sub-constant error was known before.

In this work, we continue and extend the study of constructing (k-)min-wise hash families from pseudorandomness for combinatorial rectangles and read-once branching programs. Our main result gives the first explicit min-wise hash families that use an optimal (up to constant) number of random bits and achieve a sub-constant (in fact, almost polynomially small) error, specifically, an explicit family of k-min-wise hash with O(k log N ) bits and 2 -O( log N log log N ) error. This improves all previous results for any k = log O(1) N under O(k log N ) bits. Our main techniques involve several new ideas to adapt the classical Nisan-Zuckerman pseudorandom generator to fool min-wise hashing with a multiplicative error.