1 citations · 1 across the 2 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)…
Quantum Communication Complexity of Distribution Testing
Aleksandrs Belovs, Arturo Castellanos, François Le Gall +2
The classical communication complexity of testing closeness of discrete distributions has recently been studied by Andoni, Malkin and Nosatzki (ICALP'19). In this problem, two play…
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…