Counting Real Roots in Polynomial-Time via Diophantine Approximation

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