All reports by Author Toshiya Itoh:

__
TR06-017
| 12th January 2006
__

Toshiya Itoh#### Improved Lower Bounds for Families of $\varepsilon$-Approximate k$-Restricted Min-Wise Independent Permutations

Toshiya Itoh

A family ${\cal F}$ of min-wise independent permutations is known to be a useful tool of indexing replicated documents on the Web. For any integer $n>0$, let $S_{n}$ be the family of al permutations on $[1,n]=\{1,2,\ldots, n\}$.

For any integer $k \in [1,n]$ and any real $\varepsilon >0$, we ...
more >>>