  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.
