Simple permutations mix even better

Abstract

Abstract We study the composition of random permutations drawn from a small family of O ( n 3 ) 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 Gowers (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 ( n 3 k 2 ), Õ ( n 2 k 2 )) random permutations from this family for any n ≥ 3 and k ≤ 2 n − 2. The Õ notation suppresses a polylogarithmic factor in k and n . © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008