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

First Steps in Symplectic Dynamics

Helmut Hofer
Institute for Advanced Study
September 26, 2011

The modern theory of dynamical systems, as well as symplectic geometry, have their origin with Poincare as one field with integrated Ideas. Since then these fields developed quite independently. Given the progress in these fields one can make a good argument why the time is ripe to bring them closer together around the core area of Hamiltonian dynamics

Tight Lower Bounds for 2-query LCCs Over Finite fields

Shubhangi Saraf
Microsoft Research; Member, School of Mathematics
September 27, 2011

A locally correctable code (LCC) is an error correcting code mapping d symbols to n symbols, such that for every codeword c and every received word r that is \delta-close to c, we can recover any coordinate of c (with high probability) by only making a few queries to r. LCCs are a stronger form of Locally Decodable Codes (LDCs) which have received a lot of attention recently due to their many applications and surprising constructions.