Constructing Families of ε-Approximate k-Wise Independent Permutations(<Special Section>Discrete Mathematics and Its Applications)

概要

論文の詳細を見る
The notion of k-wise independent permutations has several applications. From the practical point of view, it often suffices to consider almost (i.e., ε-approximate) k-wise independent permutation families rather than k-wise independent permutation families, however, we know little about how to construct families of ε-approximate fc-wise independent permutations of small size. For any n > 0, let S_n be the set of all permutations on {0,1,... ,n-1}. In this paper, we investigate the size offamilies of e-approximate k-wise independent permutations and show that (1) for any constant ε ≥ 0, if a family F ⊆ S_n of permutations is ε-approximate k-wiseindependent, then |F| ≥ n(n-1)・・・(n-k+1)if ε < 1; |F| ≥ {n(n-1)・・・(n-k+1)}/(1+ε) otherwise; (2) foranyconstant0 < ε ≥ 1, there exists a family F ⊆ S_n of ε-approximate k-wise independent permutations such that |F| = O(kln n)/(ε^2)n(n-1)・・・(n-k+1)); (3) for any constant ε > 0 and any n = p^m - 1 with p prime, it is possible to construct a polynomial time samplable family F ⊆ S_n of ε-approximate pairwise independent permutations such that |F| = O(n(n-1)/ε); (4) for any constant ε > 0 and any n = p^m with p prime, it is possible to construct a polynomial time samplable family F ⊆ S_n of ε-approximate 3-wise independent permutations such that |F| = O(n(n-1)(n-2)/ε). Our results are derived by combinatorial arguments, i.e., probabilistic methods and linear algebra methods.
社団法人電子情報通信学会の論文
2004-05-01

Constructing Families of ε-Approximate k-Wise Independent Permutations(<Special Section>Discrete Mathematics and Its Applications)

スポンサーリンク

概要

著者

関連論文

スポンサーリンク