ECCC-Report TR06-017https://eccc.weizmann.ac.il/report/2006/017Comments and Revisions published for TR06-017en-usTue, 07 Feb 2006 20:47:11 +0200
Paper TR06-017
| Improved Lower Bounds for Families of $\varepsilon$-Approximate k$-Restricted Min-Wise Independent Permutations |
Toshiya Itoh
https://eccc.weizmann.ac.il/report/2006/017A 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 say that a family ${\cal F} \subseteq S_{n}$ of permutations is $\varepsilon$-approximate $k$-restricted min-wise independent} if for any (nonempty) $X \subseteq [1,n]$ such that $||X|| \leq k$ and any $x \in X$, $|\Pr [\min \{\pi(X)\} = \pi(x)]- 1/\card{X}| \leq \varepsilon/|||X||$, when $\pi$ is chosen from
${\cal F}$ uniformly at random (where $||A||$ is the cardinality of a finite set $A$). For the size of families ${\cal F} \subseteq S_{n}$ of $\varepsilon$-approximate $k$-restricted min-wise independent permutations,
the following results are known: For any integer $k\in [1,n]$ and any real
$\varepsilon > 0$,
(constructive upper bound)
$||{\cal F}|| = 2^{4k+0(k)}k^{2 \log \log n/\varepsilon)}$;
(nonconstructive upper bound)
$||{\cal F}} = O(\frac{k^{2}}{\varepsilon^{2}} \log (n/k))$;
(lower bound) $||{\cal F}|| = \Omega(k^{2}(1-\sqrt{8 \varepsilon}))$.
In this paper, we first derive an upper bound for the Ramsey number of the edge coloring with $m \geq 2$ colors of a complete graph $K_{\ell}$ of $\ell$ vertices, and by the linear algebra method, we then derive an improved lower bound, i.e., we show that for any family ${\cal F} \subseteq S_{n}$ of $\varepsilon$-approximate $k$-restricted min-wise independent permutations, $||{\cal F}|| = \Omega\left(k \sqrt{\frac{1}{\varepsilon}\log (n/k)}\right)$.
Tue, 07 Feb 2006 20:47:11 +0200https://eccc.weizmann.ac.il/report/2006/017