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

Overview

Research

Identity

Additional Document Info

Other

View All

Overview

abstract

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.