What is the most efficient algorithm to compute polynomial coefficients from its roots?

Given $n$ roots, $x_1, x_2, \dotsc, x_n$, the corresponding monic polynomial is

$$y = (x-x_1)(x-x_2)\dotsm(x-x_n) = \prod_{i}^n (x - x_i)$$

To get the coefficients, i.e., $y = \sum_{i}^n a_i x^i$, a straightforward expansion requires $O \left(n^2\right)$ steps.

Alternatively, if $x_1, x_2, \dotsc, x_n$ are distinct, the problem is equivalent to polynomial interpolation with $n$ points: $(x_1, 0), (x_2, 0), \dotsc, (x_n, 0)$. The fast polynomial interpolation algorithm can be run in $O \left( n \log^2(n) \right)$ time.

I want to ask whether there is any more efficient algorithm better than $O \left(n^2\right)$? Even if there are duplicated values among $\{x_i\}$? If it helps, we can assume that the polynomial is over some prime finite field, i.e., $x_i \in \mathbf{F}_q$.

This can be done in $O(n \log^2 n)$ time, even if the $x_i$ have duplicates, via the following divide-and-conquer method.

First compute the coefficients of the polynomial $f_0(x)=(x-x_1) \cdots (x-x_{n/2})$ (via a recursive call to this algorithm). Then compute the coefficients of the polynomial $f_1(x)=(x-x_{n/2+1})\cdots(x-x_n)$. Next, compute the coefficients of $f(x)=f_0(x)f_1(x)$ using FFT-based polynomial multiplication.

This yields an algorithm whose running time satisfies the recurrence

$$T(n) = 2 T(n/2) + O(n \log n).$$

The solution to this recurrence is $T(n) = O(n \log^2 n)$. This all works even if there are duplicates in the $x_i$.

(You might also be interested in Multi-point evaluations of a polynomial mod p.)

StackExchange Computer Science Q#116643, answer score: 25