<p>Yes.  You can generate a random polynomial of degree <span class="math-container">$k$</span>, then evaluate this polynomial at <span class="math-container">$n$</span> different points in <span class="math-container">$\tilde{O}(n)$</span> time using the DFT (the DFT lets you evaluate a polynomial of degree <span class="math-container">$n$</span> at <span class="math-container">$n$</span> different points in <span class="math-container">$\tilde{O}(n)$</span> time).</p>

CC BY-SA 4.0
2019-09-25T13:27:21.010Z
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).
smapers
CC BY-SA 4.0
2019-09-25T17:03:29.497Z
@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.
D.W.
CC BY-SA 4.0
2019-09-26T06:58:21.977Z
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?
smapers
CC BY-SA 4.0
2019-09-26T15:58:06.130Z
@smapers, Yes.  The DFT works over finite fields, too; see e.g. https://en.wikipedia.org/wiki/Discrete_Fourier_transform_(general)#Number-theoretic_transform.
D.W.
CC BY-SA 4.0
2019-09-24T21:23:06.953Z
2019-09-24T21:23:06.953Z
D.W.
<p>Consider a randomized algorithm with runtime <span class="math-container">$n$</span>, which succeeds with high probability. The algorithm uses <span class="math-container">$O(n)$</span> uniformly random bits.</p>

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

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

<randomized-algorithms><derandomization><k-wise-independence>
Efficient randomness reduction using k-wise independence
smapers
# Efficient randomness reduction using k-wise independence

(Asked by: username_0 on 2019-09-24)

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)$.

**Tags:** randomized-algorithms, derandomization, k-wise-independence


---

## 1 answers

### Answer by username_1 on 2019-09-24. Score: 4 | Accepted answer

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).

> **Comments:**
> **username_0**: 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).  
> **username_1**: @username_0, 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.  
> **username_0**: 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?  
> **username_1**: @username_0, Yes.  The DFT works over finite fields, too; see e.g. https://en.wikipedia.org/wiki/Discrete_Fourier_transform_(general)#Number-theoretic_transform.  

---

