Finding the roots of a complex polynomial is in general extremely numerically unstable, as discussed in (1). According to Pan ((2), (3)), this produces a cubic complexity lower bound, and he presents a near-optimal algorithm which is quasilinear in arithmetic and quasicubic in boolean (control flow) complexity. His algorithm is an improvement to the splitting circle method.
However, this lower bound applies only if we want forward stable (i.e., correct) answers. If we're satisfied with backward stable answers, where it's okay to find correct roots for a slightly modified input problem, I would expect much faster complexities to be possible. Does anyone know if such an algorithm exists, and specifically if a splitting circle variant can run in quasilinear time if we only need backward stability?
Note: $\epsilon$ in $\tilde{O}(n \log(1/\epsilon))$ vaguely refers to the relative backward accuracy of the result (the amount you have to shift the coefficients to move to the roots to the computed answers). I'm not sure exactly what the correct definition of $\epsilon$ would be, since different coefficients can change the polynomial values by dramatically different amounts.