Conference abstracts

Session C6 - Real-Number Complexity

July 19, 17:30 ~ 17:55 - Room B7

An update on the $fg+1$ problem for Newton polygons

Pascal Koiran

Ecole Normale Supérieure de Lyon, France   -   pascal.koiran@ens-lyon.fr

Let $f$, $g$ be bivariate polynomials with at most $t$ monomials each. The product $fg$ can have up to $t^2$ monomials, but only $2t$ of them can appear as vertices of the Newton polygon of $fg$. If we add a constant (say, the constant 1) to this product, the determination of the maximum number of vertices of the corresponding Newton polygon becomes quite difficult. This is due to possible cancellations with the constant term of $fg$ (which may expose some monomials from the interior of the Newton polygon of $fg$).

This problem is motivated by a connection to an algebraic version of the P versus NP problem, as explained in my paper on the "tau-conjecture for Newton polygons" (joint work with Natacha Portier, Sébastien Tavenas and Stéphan Thomassé).

In this talk I will present some connections with problems from combinatorial geometry, and some results obtained by William Aufort for his Master's degree. His internship report is available at:

http://perso.ens-lyon.fr/pascal.koiran/Publis/aufort.pdf

View abstract PDF



FoCM 2017, based on a nodethirtythree design.