[METRIC 2011] Shachar Lovett

METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France)
Workshop on Expanders and derandomization (March 21-25, 2011)
Mar 21, 13:30-14:30 - Shachar Lovett (IAS Princeton)
Weighted families of k-wise independent permutations
---
A family of permutations in S_n is k-wise independent if a uniform permutation chosen from this family maps any distinct k elements to any distinct k elements equally likely. Efficient constructions of k-wise independent permutations are known for k=2 and k=3, but are unknown for k>=4. In fact, it is known that there are no non-trivial subgroups of S_n which are k-wise independent for k>=4 and n>=25. Faced with this adversity, research has turned towards constructing almost k-wise independent families, where small errors are allowed. Such families were constructed by Kaplan, Naor and Reingold; and can also be obtained from Kassabov's explicit set of generators of S_n which forms an expander.

In this work we consider a different model: distributions with small support which are perfectly k-wise independent. That is, we allow elements ot have non-uniform weights. We first show that a random set of size n^{O(k)} supports a k-wise independent distribution w.h.p, and that this distribution can be found efficiently. We then derandomize the construction, giving explicit such sets, and hence an efficient deterministic algorithm to find k-wise independent distributions with support size n^{O(k)}.

Joint work with Noga Alon.