Theory of Computing
-------------------
Title : Almost $k$-Wise vs. $k$-Wise Independent Permutations, and Uniformity for General Group Actions
Authors : Noga Alon and Shachar Lovett
Volume : 9
Number : 15
Pages : 559-577
URL : http://www.theoryofcomputing.org/articles/v009a015
Abstract
--------
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.