  Let $p\in\mathbb{Z}[x]$ be an arbitrary polynomial of degree $n$ with $k$
non-zero integer coefficients of absolute value less than $2^\tau$. In this
paper, we answer the open question whether the real roots of $p$ can be
computed with a number of arithmetic operations over the rational numbers that
is polynomial in the input size of the sparse representation of $p$. More
precisely, we give a deterministic, complete, and certified algorithm that
determines isolating intervals for all real roots of $p$ with
$O(k^3\cdot\log(n\tau)\cdot \log n)$ many exact arithmetic operations over the
rational numbers.
  When using approximate but certified arithmetic, the bit complexity of our
algorithm is bounded by $\tilde{O}(k^4\cdot n\tau)$, where $\tilde{O}(\cdot)$
means that we ignore logarithmic. Hence, for sufficiently sparse polynomials
(i.e. $k=O(\log^c (n\tau))$ for a positive constant $c$), the bit complexity is
$\tilde{O}(n\tau)$. We also prove that the latter bound is optimal up to
logarithmic factors.
