Generating k-independent variables in constant time

Tobias Lybecker Christiani, Rasmus Pagh

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review


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.
Original languageEnglish
Title of host publicationFoundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on
Publication date2014
ISBN (Print)978-1-4799-6517-5
Publication statusPublished - 2014


  • Randomness
  • Pseudorandomness
  • k-independence
  • Hashing
  • Expanders
  • Generators


Dive into the research topics of 'Generating k-independent variables in constant time'. Together they form a unique fingerprint.

Cite this