Consider a randomized algorithm with runtime $n$, which succeeds with high probability. The algorithm uses $O(n)$ uniformly random bits.

Now it is given that we can replace these uniformly random bits by $k$-wise independent bits, where $k$ depends on $n$ (say $k = \sqrt{n}$). Can we then reduce the number of random bits to $\tilde{O}(k)$ while keeping a runtime $\tilde{O}(n)$?

Clearly we could use k-wise independent bit generators (such as a random polynomial). However, naively implementing this would cost $\tilde{O}(k)$ steps per call, potentially increasing the runtime to $\tilde{O}(n k)$.


Yes. You can generate a random polynomial of degree $k$, then evaluate this polynomial at $n$ different points in $\tilde{O}(n)$ time using the DFT (the DFT lets you evaluate a polynomial of degree $n$ at $n$ different points in $\tilde{O}(n)$ time).

  • $\begingroup$ Is this easy to see for $n$ arbitrary points? Anyway a formal proof seems to be given in the paper "Fast modular transforms via division" by Moenck and Borodin (SWAT '72). $\endgroup$ – smapers Sep 25 '19 at 13:27
  • $\begingroup$ @smapers, no, it doesn't work for arbitrary points (as far as I know). But for this application you don't need to evaluate the polynomial at arbitrary points; it suffices to evaluate it at any $n$ points that are convenient. If you found a citation, I encourage you to write an answer of your own providing a reference to this result. $\endgroup$ – D.W. Sep 25 '19 at 17:03
  • $\begingroup$ You need to evaluate the polynomial at $n$ points of the field $F_p$ for some prime $p \geq n$ (so $n$ distinct integers). Am I correct that DFT only allows to evaluate the polynomial at the $n$ roots of unity? $\endgroup$ – smapers Sep 26 '19 at 6:58
  • 1
    $\begingroup$ @smapers, Yes. The DFT works over finite fields, too; see e.g. en.wikipedia.org/wiki/…. $\endgroup$ – D.W. Sep 26 '19 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.