If I have the roots of a polynomial, $r_1, r_2,\ldots, r_n$ is there a fast way (hopefully sub-quadratic) to find the expanded polynomial (or equivalently its coefficients)?
I know of Vieta's formula and using dynamic programming it seems as though you can do this in polynomial-time, but I am hoping for within log-factors of linear.
Thanks in advance, Pat
If the roots of $f(x) = c_nx^n + c_{n-1}x^{n-1} + \ldots + c_0$ are $r_1, r_2, \ldots, r_n$, then: $$ f(x) = c_n(x-r_1)(x-r_2)\cdots(x-r_n) \tag{*} $$ If you only have the $r_i$, then you can't determine $c_n$. If you know $c_n$, then formal multiplication of the product $(*)$ will be much better than using Vieta's formulas. I don't see how dynamic programming is of any use here.