6 citations · 6 across the 4 of their papers we have counts for
5 papers
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 fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant
Hervé Fournier, Sylvain Perifel, Rémi de Verclos
Assuming the Generalised Riemann Hypothesis (GRH), we show that for all k, there exist polynomials with coefficients in $\MA$ having no arithmetic circuits of size O(n^k) over the…
Computing the Gromov hyperbolicity of a discrete metric space
Hervé Fournier, Anas Ismail, Antoine Vigneron
We give exact and approximation algorithms for computing the Gromov hyperbolicity of an n-point discrete metric space. We observe that computing the Gromov hyperbolicity from a fix…
Monomials in arithmetic circuits: Complete problems in the counting hierarchy
Hervé Fournier, Guillaume Malod, Stefan Mengel
We consider the complexity of two questions on polynomials given by arithmetic circuits: testing whether a monomial is present and counting the number of monomials. We show that th…
A deterministic algorithm for fitting a step function to a weighted point-set
Hervé Fournier, Antoine Vigneron
Given a set of n points in the plane, each point having a positive weight, and an integer k>0, we present an optimal O(n \log n)-time deterministic algorithm to compute a step func…