Randomization, Sums of Squares, and Faster Real Root Counting for Tetranomials and Beyond

Osbert Bastani, Christopher J. Hillar, Dimitar Popov +1

Suppose f is a real univariate polynomial of degree D with exactly 4 monomial terms. We present an algorithm, with complexity polynomial in log D on average (relative to the stable…