Generating k-independent variables in constant time

Tobias Christiani, Rasmus Pagh

The generation of pseudorandom elements over finite fields is fundamental to the time, space and randomness complexity of randomized algorithms and data structures. We consider the…