Quantum communication complexity of distribution testing

Autor: Alexander A. Sherstov, François Le Gall, Guillaume Malod, Aleksandrs Belovs, Arturo Castellanos

Publikováno v: Quantum Information and Computation. 21:1261-1273

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 players each receive $t$ samples from one distribution over $[n]$, and the

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9d4be9b3ce100916be00320ec7d584e7
https://doi.org/10.26421/qic21.15-16-1

Universal relations and #P-completeness

Autor: Guillaume Malod, Hervé Fournier

Publikováno v: Theoretical Computer Science. 407(1-3):97-109

This paper follows the methodology introduced by Agrawal and Biswas in [Manindra Agrawal, Somenath Biswas, Universal relations, in: Structure in Complexity Theory Conference, 1992, pp. 207–220], based on a notion of universality for the relations a

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::61acc9e8ba976461e4beb53911c5a5e5

Characterizing Valiant's algebraic complexity classes

Autor: Guillaume Malod, Natacha Portier

Publikováno v: Journal of Complexity. 24:16-38

Valiant introduced 20 years ago an algebraic complexity theory to study the complexity of polynomial families. The basic computation model used is the arithmetic circuit, which makes these classes very easy to define and open to combinatorial techniq

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9dbe475c53b18a9d137aee726b46fa32
https://doi.org/10.1016/j.jco.2006.09.006

Lower bounds for depth 4 formulas computing iterated matrix multiplication

Autor: Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan

Publikováno v: STOC

We study the arithmetic complexity of iterated matrix multiplication. We show that any multilinear homogeneous depth 4 arithmetic formula computing the product of d generic matrices of size n × n, IMMn,d, has size nΩ(√d) as long as d = nO(1). Thi

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::042da779e03152b4a6ae7e6f566e3cf7
https://doi.org/10.1145/2591796.2591824

Monomials in arithmetic circuits: Complete problems in the counting hierarchy

Autor: Stefan Mengel, Guillaume Malod, Hervé Fournier

Publikováno v: Symposium on Theoretical Aspects of Computer Science
STACS'12 (29th Symposium on Theoretical Aspects of Computer Science)
STACS'12 (29th Symposium on Theoretical Aspects of Computer Science), Feb 2012, Paris, France. pp.362-373

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 these problems are complete for subclasses of the counting hierarchy whi

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1f075acabef045240ea53203e04550b2