Heng Cao, Haifeng Xi, et al.
WSC 2003
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.
Heng Cao, Haifeng Xi, et al.
WSC 2003
Kafai Lai, Alan E. Rosenbluth, et al.
SPIE Advanced Lithography 2007
L Auslander, E Feig, et al.
Advances in Applied Mathematics
Fausto Bernardini, Holly Rushmeier
Proceedings of SPIE - The International Society for Optical Engineering