Random polynomials and expected complexity of bisection methods for real solving
Ioannis Z. Emiris, André Galligo, Elias Tsigaridas · 2010
Our probabilistic analysis sheds light to the following questions: Why do random polynomials seem to have few, and well separated real roots, on the average? Why do exact algorithms for real root isolation may perform comparatively well or even better than numerical ones?