M. Tismenetsky
International Journal of Computer Mathematics
We study the composition of random permutations drawn from a small family of O(n3) simple permutations on (0, 1)n. Specifically, we ask how many randomly selected simple permutations need be composed to yield a permutation that is close to k-wise independent. We improve on the results of Cowers (Combin Probab Comput 5 (1996) 119-130) and Hoory et al. (Presented at 31st ICALP 2004) and show that it suffices to compose min(O(n3k 2), Õ(n2k2)) random permutations from this family for any n ≥ 3 and k ≤ 2n - 2. The Õ notation suppresses a poly logarithmic factor in k and n. © 2007 Wiley Periodicals, Inc.
M. Tismenetsky
International Journal of Computer Mathematics
Charles A Micchelli
Journal of Approximation Theory
Mario Blaum, John L. Fan, et al.
IEEE International Symposium on Information Theory - Proceedings
Hannaneh Hajishirzi, Julia Hockenmaier, et al.
UAI 2011