Constructions of k-wise almost independent permutations have been receiving a growing amount of attention in recent years. However, unlike the case of k-wise independent functions, the size of previously constructed families of such permutations is far from optimal.

In this paper we describe a method for reducing the size of families given by previous constructions. Our method relies on pseudorandom generators for space-bounded computations. More specifically, we show that a weaker derandomization tool suffices: all we need is a generator that produces ``pseudorandom walks" on undirected graphs with a consistent labelling. Such generators with sufficiently good parameters are implied by the proof that undirected connectivity is in logspace of Reingold, and made explicit by Reingold, Trevisan and Vadhan.

With this approach we are able to obtain families of k-wise almost independent permutations of size that is optimal up to polynomial factor. More precisely, if the distance from uniform for any k tuple should be at most delta, then the size of the description of a permutation in the family is O(kn + log 1/delta).