Georgia Institute of Technology College of Sciences

Suppose f is a Laurent polynomial in n variables with degree d, exactly (n+2) monomial terms, and all its coefficients in {-H,...,H} for some positive integer H. Suppose further that the exponent vectors of f do not all lie in an affine hyperplane: Such a set of exponent vectors is referred to as a circuit. We prove that the positive zero set of f is isotopic to the real zero set of an explicit n-variate quadric q, and give a fast algorithm to explicitly compute q: The bit complexity is (log(dH))^O(n). The best previous bit-complexity bounds were of the form (dlog(H))^{\Omega(n)} (to compute a data structure called a roadmap). Our results also extend to real zero sets of n-variate exponential sums over circuits. Finally, we discuss how to approach the next case up: n-variate polynomials with exactly (n+3) terms.