27 citations · 53 across the 10 of their papers we have counts for
14 papers
Approximate Polynomial Satisfiability is in the Counting Hierarchy
Nikhil Balaji, Mahsa Shirmohammadi, Sébastien Tavenas +1
The Approximate polynomial satisfiability problem (APS), introduced by Guo, Saxena, and Sinhababu (CCC 2018), asks whether the zero vector lies in the Zariski closure of the image…
On Closure Properties of Read-Once Oblivious Algebraic Branching Programs
Jules Armand, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen +3
We investigate the closure properties of read-once oblivious Algebraic Branching Programs (roABPs) under various natural algebraic operations and prove the following. - Non-closure…
The Algebraic Cost of a Boolean Sum
Ian Orzel, Srikanth Srinivasan, Sébastien Tavenas +1
It is a well-known fact that the permanent polynomial is complete for the complexity class VNP, and it is largely suspected that the determinant does not share this property, despi…
Rational and lacunary algebraic curves
Georges Comte, Sébastien Tavenas
We give a bound on the number of intersection points in a ball of the complex plane, between a rational curve and a lacunary algebraic curve . This bound depends…
Towards Optimal Depth-Reductions for Algebraic Formulas
Hervé Fournier, Nutan Limaye, Guillaume Malod +2
Classical results of Brent, Kuck and Maruyama (IEEE Trans. Computers 1973) and Brent (JACM 1974) show that any algebraic formula of size s can be converted to one of depth O(log s)…
On the Markov numbers: fixed numerator, denominator, and sum conjectures
Clément Lagisquet, Edita Pelantová, Sébastien Tavenas +1
The Markov numbers are the positive integer solutions of the Diophantine equation . Already in 1880, Markov showed that all these solutions could be generat…
Log-concavity and lower bounds for arithmetic circuits
Ignacio García-Marco, Pascal Koiran, Sébastien Tavenas
One question that we investigate in this paper is, how can we build log-concave polynomials using sparse polynomials as building blocks? More precisely, let $f = \sum\_{i = 0}^d a\…
Building Efficient and Compact Data Structures for Simplicial Complexes
Jean-Daniel Boissonnat, Karthik C. S., Sébastien Tavenas
The Simplex Tree (ST) is a recently introduced data structure that can represent abstract simplicial complexes of any dimension and allows efficient implementation of a large range…
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…
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…