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

Computer Science/Discrete Mathematics Seminar II
Topic:Existence of Small Families of t-wise Independent Permutations and t-Designs Via Local Limit Theorems
Speaker:Shachar Lovett
Affiliation:Member, School of Mathematics
Date:Tuesday, September 20
Time/Room:10:30am - 12:30pm/S-101
Video Link:https://video.ias.edu/csdm/lovett-small-families

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)} . 2. A t-(v,k,lambda) design is a family of sets of size k in a universe of size v such that each t elements belong to exactly lambda sets. Constructions of t-designs are known only for some specific settings of parameters. We show that there exist small t-designs for any t,v,k whose size is v^{O(t)}. The main technical ingredients in both cases are local limit theorems used to study random walks on lattices. Joint work with Greg Kuperberg and Ron Peled