Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9657689 | Theoretical Computer Science | 2005 | 11 Pages |
Abstract
We study the random composition of a small family of O(n3) 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, n3k3 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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Shlomo Hoory, Avner Magen, Steven Myers, Charles Rackoff,