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(n^2)$ steps.

Alternatively, if $x_1, x_2, \dotsc, x_n$ are distinct with each other. 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(n\log^2(n))$ time.

I want to ask whether there is any more efficient algorithm better than $O(n^2)$? 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.)