Notes of Shachar Lovett’s talk

{k}-wise independent permutations

1. {k}-wise independence

Definition 1 Say a set {S\subset\mathfrak{S}_n} of permutations is {k}-wise independent if it maps {k}-tuple of elements to {k}-tuples as if randomly chosen, i.e.

\displaystyle  \begin{array}{rcl}  \forall I,\,J\subset[n],\quad \mathop{\mathbb P}_{\pi\in S}(\pi(I)=J)=\frac{1}{n(n-1)\cdots(n-k+1)}. \end{array}

There are constructions for {k=2} (consider the set of affine maps on a finite field) and {k=3} (consider projective transformations on a finite projective line). It is known that no subgroup (other than {\mathfrak{A}_n} or {\mathfrak{S}_n}) can be {k}-wise independent for {k\geq 4}.

1.1. Almost {k}-wise independence

Definition 2 Say a set {S\subset\mathfrak{S}_n} of permutations is {\epsilon}-almost {k}-wise independent if it maps {k}-tuple of elements to {k}-tuples as if randomly chosen, i.e.

\displaystyle  \begin{array}{rcl}  \forall I,\,J\subset[n],\quad |n(n-1)\cdots(n-k+1)\mathop{\mathbb P}_{\pi\in S}(\pi(I)=J)-1|\leq\epsilon. \end{array}

There are efficient constructions giving {|S|=n^{o(k)}(\frac{1}{\epsilon})^{O(1)}}.

  1. Kassabov’s explicit generating set than turns {\mathfrak{S}_n} into an expander.
  2. Kaplan, Naor and Reingold (zig-zag)-derandomized long random walk.

Wigderson: Gowers and co-authors have a result similar to Kassabov’s.

1.2. {k}-wise independent distributions

It turns out that it is much easier to find distributions which are {k}-wise independent.

Definition 3 Say a distribution {D} on {\mathfrak{S}_n} is {k}-wise independent if

\displaystyle  \begin{array}{rcl}  \forall I,\,J\subset[n],\quad \mathop{\mathbb P}_{\pi\in D}(\pi(I)=J)=\frac{1}{n(n-1)\cdots(n-k+1)}. \end{array}

The point is to have as small support as possible. E.g. {n^{O(k)}}.

Claim. Let {M_k (\pi)} denote the matrix of {\pi} as a permutation of {k}-tuples. Then a subset {S\subset\mathfrak{S}_n} supports a {k}-wise independent distribution iff the convex hull of all {M_n (\pi)}, {\pi\in S} contains the matrix {\mathcal{J}} with all entries equal to {\frac{1}{n(n-1)\cdots(n-k+1)}}. Furthermore, once the support is given, the distribution can be computed.

1.3. Constructing {k}-wise independent distributions

Lemma 4 A randomly chosen subset {S\subset \mathfrak{S}_n} of size {n^{O(k)}} supports a {k}-wise independent distribution with high probability.

Proof: If not, there exists a hyperplane separating {\mathcal{J}} from the {M_k (\pi)}‘s, {\pi\in S}. The number of hyperplanes is {\leq n^{k}}, so the number of partitions by hyperplanes is {\leq e^{n^{O(k)}}}. Clearly

By Carathéodory’s theorem, {\mathcal{J}} belongs to the convex hull of {r} permutation matrices, {r\leq n^{O(k)}}. Since {\mathcal{J}} is {\mathfrak{S}_n}-invarfiant, this also holds for all left translates of these matrices…. \Box

Our main theorem is a derandomization of the Lemma.

Theorem 5 If {S} is {n^{-O(k)}}-almost {2k}-wise independent, then

  1. {S} supports a {k}-wise independent distribution.
  2. The uniform distribution on {S} is {n^{-O(k)}}-close in statistical distance to a perfect {k}-wise independent distribution.

Remark 1 One can derandomize one-sided algorithms which work for all {k}-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 {G} acting on a set {X}, say a distribution {D} is {X}-uniform if for all {x}, {y\in X},

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb P}_{g\in D}(gx=y)=\mathop{\mathbb P}_{g\in G}(gx=y). \end{array}

There is an {\epsilon}-version. What we prove is

Theorem 6 If {S} is {|X|^{-1}}-almost uniform on {X\times X}, then

  1. {S} supports a {X}-uniform distribution.
  2. The uniform distribution on {S} is close to a perfect {X}-uniform distribution.

Proof: Let {S\subset G} be almost {X\times X}-uniform. Assume the uniform matrix does not belong to the convex hull of all {M_{g}}‘s. Then there exist numbers {a_{x,y}} such that for all {x} and {g},

\displaystyle  \begin{array}{rcl}  L(g)=\sum_{y}A_{x,y}(M_x (g)_{x,y}>0. \end{array}

Use some linear representation theory.

Lemma 1: {\mathop{\mathbb E}_{g\in G}L(g)^2 \sim\mathop{\mathbb E}_{g\in S}L(g)^2}.

Lemma 2: {\max_{g\in G}L(g)\leq |X|^{O(1)}\sqrt{\mathop{\mathbb E}_{g\in G}L(g)}}.

Normalize so that {\mathop{\mathbb E}_{g\in G}L(g)^2 =1}. Then

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb E}_{g\in S}L(g)^2 \geq \frac{1}{|X|^{O(1)}}\mathop{\mathbb E}_{g\in G}L(g)^2 =\frac{1}{|X|^{O(1)}}.... \end{array}

\Box

Problem: Find combinatorial constructions of {k}-wise independent distributions.

About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See http://www.math.ens.fr/metric2011/
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s