17 citations · 133 across the 31 of their papers we have counts for
4 papers · 1 filter
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…