On the Boolean complexity of real root refinement

Overview & Synopsis

We assume that a real square-free polynomial $A$ has a degree $d$, a maximum coefficient bitsize $\tau$ and a real root lying in an isolating interval and having no nonreal roots nearby (we quantify this assumption). Then, we combine the {\em Double Exponential Sieve} algorithm (also called the {\em Bisection of the Exponents}), the bisection, and Newton iteration to decrease the width of this inclusion interval by a factor of $t=2^{-L}$. The algorithm has Boolean complexity ${\widetilde{\mathcal{O}}_B}(d^2 \tau + d L )$. Our algorithms support the same complexity bound for the refinement of $r$ roots, for any $r\le d$.