27 citations · 53 across the 10 of their papers we have counts for
5 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…
The complexity of Shortest Common Supersequence for inputs with no identical consecutive letters
Aurélie Lagoutte, Sébastien Tavenas
The Shortest Common Supersequence problem (SCS for short) consists in finding a shortest common supersequence of a finite set of words on a fixed alphabet Sigma. It is well-known t…
Detecting wheels
Emilie Diot, Sébastien Tavenas, Nicolas Trotignon
A \emph{wheel} is a graph made of a cycle of length at least~4 together with a vertex that has at least three neighbors in the cycle. We prove that the problem whose instance is a…
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…
Improved bounds for reduction to depth 4 and depth 3
Sébastien Tavenas
Koiran showed that if a -variate polynomial of degree (with ) is computed by a circuit of size , then it is also computed by a homogeneous circuit of depth fo…