**-wise independent permutations**

**1. -wise independence **

Definition 1Say 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 2Say 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 3Say 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 4A 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 5If 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 1One 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 6If 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.