15 citations · 72 across the 13 of their papers we have counts for
14 papers
Computing the multilinear factors of lacunary polynomials without heights
Arkadev Chattopadhyay, Bruno Grenet, Pascal Koiran +2
We present a deterministic algorithm which computes the multilinear factors of multivariate lacunary polynomials over number fields. Its complexity is polynomial in where…
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…
Counting Tropically Degenerate Valuations and p-adic Approaches to the Hardness of the Permanent
Pascal Koiran, Natacha Portier, J. Maurice Rojas
The Shub-Smale Tau Conjecture is a hitherto unproven statement (on integer roots of polynomials) whose truth implies both a variant of (for the BSS model over C) and the…
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…