Bruno Grenet
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Bruno Grenet has a total of 3 co-authors. Here are the top co-authors by number of shared publications:
- Natacha Portier
UMR 5668 ENS Lyon -CNRS -UCBL -INRIA Université de Lyon
2 shared publications - Pascal Koiran
EnsL Univ Lyon UCBL CNRS LIP F-69342 Cedex 07 LYON France
2 shared publications Laboratoire de L’iNformatique du Parallélisme École Normale Supérieure de Lyon
1 shared publication
Latest Publications
- 30 April 2013
- Published by Elsevier in Journal of Complexity
- Vol. 29 (2) , 142-157
On the complexity of the multivariate resultant
- 30 April 2013
- Published by Elsevier in Journal of Complexity
- Vol. 29 (2) , 142-157
On the complexity of the multivariate resultant
- Open Access
The Multivariate Resultant is NP-hard in any Characteristic
The multivariate resultant is a fundamental tool of computational algebraic geometry. It can in particular be used to decide whether a system of n homogeneous equations in n variables is satisfiable (the resultant is a polynomial in the system's coefficients which vanishes if and only if the system is satisfiable). In this paper we present several NP-hardness results for testing whether a multivariate resultant vanishes, or equivalently for deciding whether a square system of homogeneous equations is satisfiable. Our main result is that testing the resultant for zero is NP-hard under deterministic reductions in any characteristic, for systems of low-degree polynomials with coefficients in the ground field (rather than in an extension). We also observe that in characteristic zero, this problem is in the Arthur-Merlin class AM if the generalized Riemann hypothesis holds true. In positive characteristic, the best upper bound remains PSPACE.
Open AccessThe Multivariate Resultant is NP-hard in any Characteristic
The multivariate resultant is a fundamental tool of computational algebraic geometry. It can in particular be used to decide whether a system of n homogeneous equations in n variables is satisfiable (the resultant is a polynomial in the system's coefficients which vanishes if and only if the system is satisfiable). In this paper we present several NP-hardness results for testing whether a multivariate resultant vanishes, or equivalently for deciding whether a square system of homogeneous equations is satisfiable. Our main result is that testing the resultant for zero is NP-hard under deterministic reductions in any characteristic, for systems of low-degree polynomials with coefficients in the ground field (rather than in an extension). We also observe that in characteristic zero, this problem is in the Arthur-Merlin class AM if the generalized Riemann hypothesis holds true. In positive characteristic, the best upper bound remains PSPACE.
- 15 December 2009
- Published by Wolfram Research, Inc. in Complex Systems
- Vol. 18 (4) , 403-426
Acceptable Complexity Measures of Theorems
- 15 December 2009
- Published by Wolfram Research, Inc. in Complex Systems
- Vol. 18 (4) , 403-426
Acceptable Complexity Measures of Theorems