Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2510.10431 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915605802647552 |
|---|---|
| author | Chen, Xue Huang, Shengtang Li, Xin |
| author_facet | Chen, Xue Huang, Shengtang Li, Xin |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_10431 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Explicit Min-wise Hash Families with Optimal Size Chen, Xue Huang, Shengtang Li, Xin Data Structures and Algorithms Discrete Mathematics 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. |
| title | Explicit Min-wise Hash Families with Optimal Size |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2510.10431 |