Fast Approximation of Polynomial Zeros and Matrix Eigenvalues

Given a black box (oracle) for the evaluation of a univariate polynomial p(x) of a degree d, we seek its zeros, that is, the roots of the equation p(x)=0. At FOCS 2016 Louis and Vempala approximated a largest zero of such a real-rooted polynomial within $1/2^b$, by performing at NR cost of the evaluation of Newton's ratio p(x)/p'(x) at O(b\log(d)) points x. They readily extended this root-finder to record fast approximation of a largest eigenvalue of a symmetric matrix under the Boolean complexity model. We apply distinct approach and techniques to obtain more general results at the same computational cost.