On Solving Fewnomials Over Intervals in Fewnomial Time

J. Maurice Rojas, Yinyu Ye

Let f be a degree D univariate polynomial with real coefficients and exactly m monomial terms. We show that in the special case m=3 we can approximate within eps all the roots of f…