# Efficient randomness reduction using k-wise independence

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).
• 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). Sep 25, 2019 at 13:27
• @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.
• 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? Sep 26, 2019 at 6:58