Improved Lower Bounds for Families of ε-Approximate k-Restricted Min-Wise Independent Permutations

摘要

A family 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{sub}n be the family of all permutations on [1, n] = {1, 2,..., n}. For any integer k such that 1 ≤ k ≤ n and any real ε > 0, we say that a family F {is contained in} S{sub}n of permutations is ε- approximate k-restricted min-wise independent if for any (nonempty) subset X {is contained in} [1, n] such that ‖X‖ ≤ k and any element x∈X, |Pr[min{π(X)} = π(X)] - ‖ X‖{sup}(-1)| ≤ ε/‖X‖, when π is chosen from F uniformly at random (where ‖A‖ denotes the cardinality of a finite set A). For the size of families F {is contained in} S{sub}n of ε-approximate k- restricted min-wise independent permutations, the following results are known: For any integer k such that 1 ≤ k ≤ n and any real ε > 0, (constructive upper bound) ‖F‖ = 2{sup}(4k+o(k)k{sup}(2loglog(n/ε)); (nonconstructive upper bound) ‖F‖ = O(k{sup}2/ε{sup}2log(n/k)); (lower bound) ‖F‖ = Ω(k{sup}2(1-(8 ε){sup}(1/2))) and ‖F‖ = Ω(min{k{sup}22{sup}(k/2) log(n/k), (log(1/ε)(logn-log(1/ε)))/(ε{sup}(1/3))}. In this paper, we first derive an upper bound for the Ramsey number of the edge coloring with m ≥ 2 colors of a complete graph K{sub}l of l vertices, and by the linear algebra method, we then derive a slightly improved lower bound, i.e., we show that for any family F{is contained in} S{sub}n of ε-approximate k-restricted min-wise independent permutations, ‖F‖ = Ω(k((1/ε)log(n/k)){sup}(1/2)).