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\subseteq[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, web page detection, and $\ell_0$ sampling. The classical works by Indyk and Pătraşcu and Thorup 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. Based on a reduction from pseudorandom generators for combinatorial rectangles by Saks, Srinivasan, Zhou and Zuckerman, Gopalan and Yehudayoff 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.

翻译：我们研究最小哈希族的显式构造及其对$k$-最小哈希族的扩展。非正式地说，最小哈希族保证对于任意固定子集$X\\subseteq[N]$，$X$中的每个元素在$X$的所有元素中具有最小值的概率相等；$k$-最小哈希族则保证$X$中每个大小为$k$的子集均满足此性质。最小哈希广泛应用于计算机科学的诸多领域，如草图算法、网页检测和$\\ell_0$采样。Indyk与Pătraşcu、Thorup的经典工作表明，$Θ(\\log(1/δ))$-独立族可产生乘法（相对）误差$δ$的最小哈希，从而得到需要$Θ(\\log(1/δ)\\log N)$随机比特的构造。基于Saks、Srinivasan、Zhou和Zuckerman关于组合矩形伪随机生成器的归约方法，Gopalan与Yehudayoff将多项式小误差$δ$所需的比特数改进为$O(\\log N\\log\\log N)$。然而，此前尚未发现能以$O(\\log N)$比特（多项式规模族）实现亚常数误差的构造。本工作中，我们延续并扩展了基于组合矩形和只读分支程序伪随机性构造（$k$‑）最小哈希族的研究。我们的主要成果首次给出了使用最优（至常数因子）随机比特数且达到亚常数（实际为近多项式小）误差的显式最小哈希族，具体而言：构造出具有$O(k\\log N)$比特和$2^{-O(\\log N/\\log\\log N)}$误差的显式$k$-最小哈希族。对于任意$k=\\log^{O(1)}N$且比特数为$O(k \\log N)$的情形，本结果改进了所有先前研究。我们的核心技术涉及若干新思路，通过调整经典Nisan-Zuckerman伪随机生成器来实现对具有乘法误差的最小哈希的欺骗。