preprint-author: 
M. Kim and S. Sutherland
preprint-title: 
Polynomial Root-Finding Algorithms and Branched Covers
preprint-abstract: 

We construct a family of root-finding algorithms which exploit the branched covering structure of a polynomial of degree $d$ with a path-lifting algorithm for finding individual roots. In particular, the family includes an algorithm that computes an $\epsilon$-factorization of the polynomial which has an arithmetic complexity of $ \mathcal{O} (d^2(log d)^2 + d(log d)^2|log \epsilon |)$. At the present time (1993), this complexity is the best known in terms of the degree.

preprint-year: 
1991