Counting Real Roots in Polynomial-Time via Diophantine Approximation. Academic Article uri icon


  • Suppose A = { a 1 , , a n + 2 } Z n has cardinality n + 2 , with all the coordinates of the a j having absolute value at most d, and the a j do not all lie in the same affine hyperplane. Suppose F = ( f 1 , , f n ) is an n n polynomial system with generic integer coefficients at most H in absolute value, and A the union of the sets of exponent vectors of the f i . We give the first algorithm that, for any fixed n, counts exactly the number of real roots of F in time polynomial in log ( d H ) . We also discuss a number-theoretic hypothesis that would imply a further speed-up to time polynomial in n as well.

published proceedings

  • Found Comut Math

altmetric score

  • 0.25

author list (cited authors)

  • Rojas, J. M.

citation count

  • 0

complete list of authors

  • Rojas, J Maurice

publication date

  • January 2022