Simple Permutations Mix Even Better

Details Simple Permutations Mix Even Better Simple Permutations Mix Even Better

2004-11-04

arxiv.org/abs/math/0411098v2

Mathematics

Combinatorics

Better statement and proof of Theorem 9

Scientific paper

We study the random composition of 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 1996 and Hoory, Magen, Myers and Rackoff 2004, and show that up to a polylogarithmic factor, n^2*k^2 compositions of random permutations from this family suffice. In addition, our results give an explicit construction of a degree O(n^3) Cayley graph of the alternating group of 2^n objects with a spectral gap Omega(2^{-n}/n^2), which is a substantial improvement over previous constructions.

Affiliated with

Also associated with

No associations

Rating

Simple Permutations Mix Even Better does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Simple Permutations Mix Even Better, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simple Permutations Mix Even Better will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-278495