Revised: January 14, 2013
Published: May 30, 2013
Abstract: [Plain Text Version]
A family of permutations in $S_n$ is $k$-wise independent if a uniform permutation chosen from the family maps any sequence of $k$ distinct elements to any sequence of $k$ distinct elements with equal probability. Efficient constructions of $k$-wise independent permutations are known for $k=2$ and $k=3$ based on multiply transitive permutation groups but are unknown for $k \ge 4$. In fact, it is known that there are no nontrivial subgroups of $S_n$ for $n \ge 25$ which are $4$-wise independent ("4-transitive"). Faced with this obstacle, research has turned towards constructing almost $k$-wise independent families, where small errors are allowed. Constructions of almost $k$-wise independent families of permutations, with optimal size up to polynomial factors, have been achieved by several authors.
Motivated by this problem, we give several results relating almost $k$-wise and $k$-wise distributions over permutations.
- Any almost $k$-wise independent distribution, with small enough error, is close in statistical distance to a $k$-wise independent distribution.
- A uniformly random set of $n^{O(k)}$ permutations supports, with high probability, a distribution which is $k$-wise independent.
- Derandomizing this, we show that any family which is almost $2k$-wise independent, with small enough error, supports a distribution which is $k$-wise independent.
These results allow for simplified analysis of randomized algorithms. For example, our results show that one can analyze an algorithm assuming access to $k$-wise independent permutation families, but then use it with only almost $k$-wise independent families, with a provable correctness guarantee.
In fact, we prove all of these results in the general setting of a group actions. Let $G$ be a group acting on a set $X$. The case of $k$-wise permutations corresponds to $G=S_n$ and $X$ the set of sequences of $k$ distinct elements. A subset $S$ of $G$ is $X$-uniform if for any $x,y \in X$, the probability over a uniform $g \in S$ that $g(x)=y$ is the same as when $g$ is chosen uniformly from $G$. It is approximately $X$-uniform if these probabilities are close. We prove all the above results in this general setting, relating almost $X$-uniform and $X$-uniform distributions. Our proof is based on basic tools from the representation theory of finite groups.
An earlier version of this paper appeared in the Proceedings of the 16th International Workshop on Randomization and Computation (RANDOM'12), pages 350--361, 2012.
Licensed under a Creative Commons Attribution License (CC-BY)