Salvatore Certo, Anh Pham, et al.
Quantum Machine Intelligence
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.
Salvatore Certo, Anh Pham, et al.
Quantum Machine Intelligence
Karthik Visweswariah, Sanjeev Kulkarni, et al.
IEEE International Symposium on Information Theory - Proceedings
James Lee Hafner
Journal of Number Theory
Daniel J. Costello Jr., Pierre R. Chevillat, et al.
ISIT 1997