Randomization, sums of squares, near-circuits, and faster real root counting
Osbert Bastani, Christopher J. Hillar, Dimitar Popov, J. Maurice Rojas · Contemporary mathematics - American Mathematical Society · 2011
Suppose that f is a real univariate polynomial of degree D with exactly 4 monomial terms. We present a deterministic algorithm of complexity polynomial in logD that, for most inputs, counts the number of real roots of f. The best previous algorithms have complexity super-linear in D. We also discuss connections to sums of squares and A-discriminants, including explicit obstructions to expressing positive definite sparse polynomials as sums of squares of few sparse polynomials. Our key theoretical tool is the introduction of efficiently computable chamber cones, which bound regions in coefficient space where the number of real roots of f can be computed easily. Much of our theory extends to n-variate (n+3)-nomials.