School of Mathematics

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)} \) .

Day 4

Institute for Advanced Study
May 12, 2011

10:00 am - 11:00 am  Melissa Liu, Columbia University, "Coherent-constructible correspondence and homological mirror symmetry II"

11:30 am - 12:30 pm  Mohammed Abouzaid, MIT, "Generation criteria for the Fukaya category II"

Day 3

Institute for Advanced Study
May 11, 2011

10:00 am - 11:00 am  Mohammed Abouzaid, MIT, "Generation criteria for the Fukaya category"

11:30 am - 12:30 pm  Dmitry Tamarkin, Northwestern, "Microlocal category for a closed symplectic manifold II"

2:30 pm - 3:30 pm     Bohan Fang, Columbia University, "Coherent-constructible correspondence and homological mirror symmetry I"