A near-optimal algorithm for computing real roots of sparse polynomials
Michael Sagraloff · 2014
Let p ∈ Z[x] be an arbitrary polynomial of degree n with k non-zero integer coefficients of absolute value less than 2τ. In this paper, we answer the open question whether the real roots of p can be computed with a number of arithmetic operations over the rational numbers that is polynomial in the input size of the sparse representation of p. More precisely, we give a deterministic, complete, and certified algorithm that determines isolating intervals for all real roots of p with O(k3·log(nτ)·logn) many exact arithmetic operations over the rational numbers.