The Bolzano Method to Isolate the Roots of a Bitstream Polynomial

Whereas the original Bolzano method assumes an integer polynomial as input, this talk will present an extension of the Bolzano method to handle square-free polynomials with arbitrary real coefficients (in bitstream representation).
The bit complexity of this new method is competitive with all previous practical approaches for real root isolation of polynomials with real coefficients (e.g. the Descartes' method).
For the special case of isolating the real roots of an integer polynomial F, our algorithm improves the bit complexity of the previous Bolzano method by a factor of n = deg F.