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