15 citations · 72 across the 13 of their papers we have counts for
9 papers · 1 filter
On the intersection of a sparse curve and a low-degree curve: A polynomial version of the lost theorem
Pascal Koiran, Natacha Portier, Sébastien Tavenas
Consider a system of two polynomial equations in two variables: where $F \in \rr[X,Y]$ has degree and $G \in \rr[X,Y]$ has monomials. We show tha…
A tau-conjecture for Newton polygons
Pascal Koiran, Natacha Portier, Sébastien Tavenas +1
One can associate to any bivariate polynomial P(X,Y) its Newton polygon. This is the convex hull of the points (i,j) such that the monomial X^i Y^j appears in P with a nonzero coef…
On the Complexity of the Multivariate Resultant
Bruno Grenet, Pascal Koiran, Natacha Portier
The multivariate resultant is a fundamental tool of computational algebraic geometry. It can in particular be used to decide whether a system of n homogeneous equations in n variab…
Factoring bivariate lacunary polynomials without heights
Arkadev Chattopadhyay, Bruno Grenet, Pascal Koiran +2
We present an algorithm which computes the multilinear factors of bivariate lacunary polynomials. It is based on a new Gap Theorem which allows to test whether a polynomial of the…
A Wronskian Approach to the real τ-conjecture
Pascal Koiran, Natacha Portier, Sébastien Tavenas
According to the real τ-conjecture, the number of real roots of a sum of products of sparse polynomials should be polynomially bounded in the size of such an expression. It is know…
The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent
Bruno Grenet, Pascal Koiran, Natacha Portier +1
Polynomial identity testing and arithmetic circuit lower bounds are two central questions in algebraic complexity theory. It is an intriguing fact that these questions are actually…