Amortized Bounds for Real Root Isolation

square-free integer polynomial f(X). One algorithm for solving
this problem is based upon the Descartes rule of signs.
The algorithm is a form of binary search and its complexity is
dependent upon the number of nodes in the search tree. We prove
that the number of nodes in the search tree is O(dL + d \lg d),
where d is the degree of f(X) and L is the bit-size of its
coefficients. This improves upon a recent bound of Krandick and
Mehlhorn by a factor of \lg d. Moreover, we show that the bound
is optimal when L = \Omega(\lg d).

This is joint work with Chee Yap and is in progress.