Daniel Perrucci: An algorithm to decide the existence of real roots of sparse univariate integer polynomials

Abstract: Let f  be a polynomial of degree D in Z[X] with exactly m non-zero coefficients and let | f |1 be the sum of the absolute values of the coefficients of f. We show an algorithm which decides, in the generic case, if f has a real root or not in O(log D + log | f |1 )2m operations; thus, our algorithm is oriented to deciding the vanishing in R of sparse polynomials. This is a joint work with Juan Sabia (in progress).