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