Simple permutations mix well

We study the random composition of a small family of O ( n 3 ) simple permutations on { 0, 1 } n. Specifically, we ask what is the number of compositions needed to achieve a permutation that is close to k -wise independent. We improve on a result of Gowers [An almost m -wise independent random permutation of the cube, Combin. Probab. Comput. 5(2) (1996) 119–130] and show that up to a polylogarithmic factor, n 3 k 3 compositions of random permutations from this family suffice. We further show that the result applies to the stronger notion of k -wise independence against adaptive adversaries. This question is essentially about the rapid mixing of the random walk on a certain graph, and we approach it using a new technique to construct canonical paths. We also show that if we are willing to use a much larger family of simple permutations then we can guarantee closeness to k -wise independence with fewer compositions and fewer random bits.

Authors

• Shlomo Hoory
• Avner Magen
• Steven Myers
• Charles Rackoff

Keywords

• Permutations
• k-wise independence
• Fast mixing
• Random walk