A Near-Optimal Algorithm for Computing Real Roots of Sparse Polynomials

Michael Sagraloff

Let $p\in \mathbb{Z}[x]$ be an arbitrary polynomial of degree $n$ with $k$ non-zero integer coefficients of absolute value less than $2^{\tau }$. In this paper, we answer the open questio…