Bivariate Fewnomials and Factorization
Martin Avendano, University of Buenos Aires, Argentina

We prove that a real bivariate polynomial f with t monomial terms has at most 6t-4 isolated zeroes on any real line, and vanishes identically on no more than 2t-1 real lines. This is the first known bound that is sub-exponential in t. As a consequence, we derive a polynomial-time algorithm to decide whether a degree 1 polynomial divides a bivariate polynomial g, over any real algebraic number field. Here, the complexity bound is polynomial in t, the log of the degree of g, and the logarithmic height of g.