A Nearly Linear Size 4-Min-Wise Independent Permutation Family by Finite Geometries

摘要

Informally, a family F is contained in S_n of permutations is k-restricted min-wise independent if for any X is contained in [0, n - 1] with |X| < k, each x ∈ X is mapped to the minimum among π(X) equally likely, and a family F is contained in S_n of permutations is k-rankwise independent if for any X is contained in [0, n - 1] with |X| ≤ k, all elements in X are mapped in any possible order equally likely. It has been shown that if a family F is contained in S_n of permutations is k-restricted min-wise (resp. k-rankwise) independent, then |F| = Ω(n~([(k-1)/2])) (resp. |F| = Ω(n~([k/2])). In this paper, we construct families F is contained in S_n of permutations of which size are close to those lower bounds for k = 3,4, i.e., we construct a family F is contained in S_n of 3-restricted (resp. 4-restricted) min-wise independent permutations such that |F| = O(n lg~2 n) (resp. |F| = O(n lg~3 n)) by applying the affine plane AG(2, q), and a family F is contained in S_n of 4-rankwise independent permutations such that |F| = O(n~3 lg~6 n) by applying the projective plane PG(2, q). Note that if a family F is contained in S_n of permutations is 4-rankwise independent, then |F| = Ω(n~2). Since a family F is contained in S_n of 4-rankwise independent permutations is 4-restricted min-wise independent, our family F is contained in S_n of 4-restricted min-wise independent permutations is the witness that properly separates the notion of 4-rankwise independence and that of 4-restricted min-wise independence.