On solving univariate sparse polynomials in logarithmic time Academic Article uri icon


  • 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 all the roots of f in the interval [0,R] using just O(log(D)log(D log R/)) arithmetic operations. In particular, we can count the number of roots in any bounded interval using just O(log2 D) arithmetic operations. Our speed-ups are significant and near-optimal: The asymptotically sharpest previous complexity upper bounds for both problems were super-linear in D, while our algorithm has complexity close to the respective complexity lower bounds. We also discuss conditions under which our algorithms can be extended to general m, and a connection to a real analogue of Smale's 17th Problem. 2004 Elsevier Inc.All rights reserved.

published proceedings


author list (cited authors)

  • Rojas, J. M., & Ye, Y. Y.

citation count

  • 11

complete list of authors

  • Rojas, JM||Ye, YY

publication date

  • January 2005