Existence of Small Families of t-wise Independent Permutations and t-Designs Via Local Limit Theorems

Shachar Lovett
Institute for Advanced Study
September 20, 2011

We show existence of rigid combinatorial objects that previously were not known to exist. Specifically, we consider two families of objects:

1. A family of permutations on n elements is t-wise independent if it acts uniformly on tuples of t elements. Constructions of small families of t-wise independent permutations are known only for \( t=1,2,3 \) . We show that there exist small families of t-wise independent permutations for all t , whose size is \( n^{O(t)} \) .