@COMMENT {Autogenerated file by bib2html.pl version 0.94}
@Article{te-tcs-2008,
  author =       {Elias~P. Tsigaridas and Ioannis~Z. Emiris},
  title =        {{On the complexity of real root isolation using
                  Continued Fractions}},
  journal =      TCS,
  volume =       392,
  pages =        {158--173},
  year =         2008,
  editor =       {L. Bus{\'e} and M. Elkadi and B. Mourrain},
  abstract =     " We present algorithmic, complexity and
                  implementation results concerning real root
                  isolation of integer univariate polynomials using
                  the continued fraction expansion of real algebraic
                  numbers.  One motivation is to explain the method's
                  good performance in practice.  %% We derive an
                  expected complexity bound of $\sOB(d^6 + d^4
                  \tau^2)$, where $d$ is the polynomial degree and
                  $\tau$ bounds the coefficient bit size, using a
                  standard bound on the expected bit size of the
                  integers in the continued fraction expansion, thus
                  matching the current worst-case complexity bound for
                  real root isolation by exact methods (Sturm,
                  Descartes and Bernstein subdivision).  %% Moreover,
                  using a homothetic transformation we improve the
                  expected complexity bound to $\sOB( d^3 \tau)$.  We
                  compute the multiplicities within the same
                  complexity and extend the algorithm to non
                  square-free polynomials.  %% Finally, we present an
                  open-source \texttt{C++} implementation in the
                  algebraic library \synaps, and illustrate its
                  completeness and efficiency as compared to some
                  other available software.  For this we use
                  polynomials with coefficient bit size up to 25\,000
                  bits and degree up to 2\,000.",
}