-wise independent permutations
1. -wise independence
Definition 1 Say a set of permutations is -wise independent if it maps -tuple of elements to -tuples as if randomly chosen, i.e.
There are constructions for (consider the set of affine maps on a finite field) and (consider projective transformations on a finite projective line). It is known that no subgroup (other than or ) can be -wise independent for .
1.1. Almost -wise independence
Definition 2 Say a set of permutations is -almost -wise independent if it maps -tuple of elements to -tuples as if randomly chosen, i.e.
There are efficient constructions giving .
- Kassabov’s explicit generating set than turns into an expander.
- Kaplan, Naor and Reingold (zig-zag)-derandomized long random walk.
Wigderson: Gowers and co-authors have a result similar to Kassabov’s.
1.2. -wise independent distributions
It turns out that it is much easier to find distributions which are -wise independent.
Definition 3 Say a distribution on is -wise independent if
The point is to have as small support as possible. E.g. .
Claim. Let denote the matrix of as a permutation of -tuples. Then a subset supports a -wise independent distribution iff the convex hull of all , contains the matrix with all entries equal to . Furthermore, once the support is given, the distribution can be computed.
1.3. Constructing -wise independent distributions
Lemma 4 A randomly chosen subset of size supports a -wise independent distribution with high probability.
Proof: If not, there exists a hyperplane separating from the ‘s, . The number of hyperplanes is , so the number of partitions by hyperplanes is . Clearly
By Carathéodory’s theorem, belongs to the convex hull of permutation matrices, . Since is -invarfiant, this also holds for all left translates of these matrices….
Our main theorem is a derandomization of the Lemma.
Theorem 5 If is -almost -wise independent, then
- supports a -wise independent distribution.
- The uniform distribution on is -close in statistical distance to a perfect -wise independent distribution.
Remark 1 One can derandomize one-sided algorithms which work for all -wise independent distributions (one-sided means that the algorithm computes given Boolean function exactly with positive probability). One merely needs to enumerate all instances.
In fact our discussion is not specific to permutations. More generally, given a group acting on a set , say a distribution is -uniform if for all , ,
There is an -version. What we prove is
Theorem 6 If is -almost uniform on , then
- supports a -uniform distribution.
- The uniform distribution on is close to a perfect -uniform distribution.
Proof: Let be almost -uniform. Assume the uniform matrix does not belong to the convex hull of all ‘s. Then there exist numbers such that for all and ,
Use some linear representation theory.
Lemma 1: .
Lemma 2: .
Normalize so that . Then
Problem: Find combinatorial constructions of -wise independent distributions.