Random Polynomials and Approximate Zeros of Newton’s Method

In this paper the authors study the size of the set of “approximate zeros” for Newton’s method, for a randomly chosen polynomial over certain distributions. For a degree d monic polynomial with coefficients chosen uniformly and independently in the unit ball, the results of this paper show, for example, that the set of approximate zeros is at least $Cd^{(-1.5-\varepsilon)}$ for any positive $\varepsilon$, with C depending only on $\varepsilon$.