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 problem of generating k-independent random values over a finite field F in a word RAM model equipped with constant time addition and multiplication in F, and present the first nontrivial construction of a generator that outputs each value in constant time, not dependent on k. Our generator has period length |F| poly log k and uses k poly (log k) log |F| bits of space, which is optimal up to a poly log k factor. We are able to bypass Siegel's lower bound on the time-space tradeoff for k-independent functions by a restriction to sequential evaluation.
|Titel||Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on|
|Status||Udgivet - 2014|