Random polynomials and expected complexity of bisection methods for real solving

Ioannis Z. Emiris, André Galligo, Elias Tsigaridas

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 algorithm…