Counting Real Roots in Polynomial-Time for Systems Supported on Circuits
share
Suppose A={a_1,…,a_n+2}⊂ℤ^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 in time polynomial in log(dH).
READ FULL TEXT