New answers tagged

4

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


Top 50 recent answers are included