  It is well known that, using fast algorithms for polynomial multiplication
and division, evaluation of a polynomial $F \in \mathbb{C}[x]$ of degree $n$ at
$n$ complex-valued points can be done with $\tilde{O}(n)$ exact field
operations in $\mathbb{C},$ where $\tilde{O}(\cdot)$ means that we omit
polylogarithmic factors. We complement this result by an analysis of
approximate multipoint evaluation of $F$ to a precision of $L$ bits after the
binary point and prove a bit complexity of $\tilde{O}(n(L + \tau + n\Gamma)),$
where $2^\tau$ and $2^\Gamma,$ with $\tau, \Gamma \in \mathbb{N}_{\ge 1},$ are
bounds on the magnitude of the coefficients of $F$ and the evaluation points,
respectively. In particular, in the important case where the precision demand
dominates the other input parameters, the complexity is soft-linear in $n$ and
$L$.
  Our result on approximate multipoint evaluation has some interesting
consequences on the bit complexity of further approximation algorithms which
all use polynomial evaluation as a key subroutine. Of these applications, we
discuss in detail an algorithm for polynomial interpolation and for computing a
Taylor shift of a polynomial. Furthermore, our result can be used to derive
improved complexity bounds for algorithms to refine isolating intervals for the
real roots of a polynomial. For all of the latter algorithms, we derive
near-optimal running times.
