  We study the complexity of computing the real solutions of a bivariate
polynomial system using the recently proposed algorithm BISOLVE. BISOLVE is a
classical elimination method which first projects the solutions of a system
onto the $x$- and $y$-axes and, then, selects the actual solutions from the so
induced candidate set. However, unlike similar algorithms, BISOLVE requires no
genericity assumption on the input nor it needs any change of the coordinate
system. Furthermore, extensive benchmarks from \cite{bes-bisolve-2011} confirm
that the algorithm outperforms state of the art approaches by a large factor.
In this work, we show that, for two polynomials $f,g\in\mathbb{Z}[x,y]$ of
total degree at most $n$ with integer coefficients bounded by $2^\tau$, BISOLVE
computes isolating boxes for all real solutions of the system $f=g=0$ using
$\Otilde(n^8\tau^{2})$ bit operations, thereby improving the previous record
bound by a factor of at least $n^{2}$.
