### DIMACS Theoretical Computer Science Seminar

Title: Existence of small families of t-wise independent permutations and t-designs via local limit theorems

Speaker: **Shachar Lovett**, Institute of Advanced Study

Date: Wednesday, September 21, 2011 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

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-(n,m,lambda) design is a family of sets of size m in a universe of size n 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 n,m whose size (and lambda) are n^{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.

See: http://paul.rutgers.edu/~yixinxu/theory-fall11.html