From Independence to Expansion and Back Again

Tobias Christiani, Rasmus Pagh, Mikkel Thorup

We consider the following fundamental problems: (1) Constructing $k$-independent hash functions with a space-time tradeoff close to Siegel's lower bound. (2) Constructing represent…