  Consider a univariate polynomial f in Z[x] with degree d, exactly t monomial
terms, and coefficients in {-H,...,H}. Solving f over the reals, R, in
polynomial-time can be defined as counting the exact number of real roots of f
and then finding (for each such root z) an approximation w of logarithmic
height (log(dH))^{O(1)} such that the Newton iterates of w have error decaying
at a rate of O((1/2)^{2^i}). Solving efficiently in this sense, using
(log(dH))^{O(1)} deterministic bit operations, is arguably the most honest
formulation of solving a polynomial equation over R in time polynomial in the
input size. Unfortunately, deterministic algorithms this fast are known only
for t=2, unknown for t=3, and provably impossible for t=4. (One can of course
resort to older techniques with complexity (d\log H)^{O(1)} for t>=4.)
  We give evidence that polynomial-time real-solving in the strong sense above
is possible for t=3: We give a polynomial-time algorithm employing
A-hypergeometric series that works for all but a fraction of 1/Omega(log(dH))
of the input f. We also show an equivalence between fast trinomial solving and
sign evaluation at rational points of small height. As a consequence, we show
that for "most" trinomials f, we can compute the sign of f at a rational point
r in time polynomial in log(dH) and the logarithmic height of r. (This was
known only for binomials before.) We also mention a related family of
polynomial systems that should admit a similar speed-up for solving.
