Natacha Portier
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
Natacha Portier has a total of 9 co-authors. Here are the top co-authors by number of shared publications:
- Pascal Koiran
EnsL Univ Lyon UCBL CNRS LIP F-69342 Cedex 07 LYON France
7 shared publications - Vincent D. Blondel
Department of Mathematical Engineering Catholic University of Louvain Avenue Georges Lemaitre 4 B-1348 Louvain-la-Neuve Belgium
4 shared publications - Bruno Grenet
Department of Computer Science LIP UMR 5668 ENS de Lyon -CNRS -UCBL -INRIA École Normale Supérieure de Lyon Université de Lyon University of Toronto
2 shared publications - Stéphane Gaubert
INRIA and CMAP École polytechnique Palaiseau France
2 shared publications - Sébastien Tavenas
Max-Planck-Insitut für Informatik
2 shared publications - Emmanuel Jeandel
LIP, Ecole Normale Superieure de Lyon, 46 allee d'Italie
1 shared publication
Latest Publications
- 30 October 2014
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 53 (1) , 48-63
On the Intersection of a Sparse Curve and a Low-Degree Curve: A Polynomial Version of the Lost Theorem
- 30 October 2014
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 53 (1) , 48-63
On the Intersection of a Sparse Curve and a Low-Degree Curve: A Polynomial Version of the Lost Theorem
- 23 October 2014
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 15 (1) , 185-197
A $\tau $ τ -Conjecture for Newton Polygons- 23 October 2014
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 15 (1) , 185-197
A $\tau $ τ -Conjecture for Newton Polygons- Open Access
A Wronskian Approach to the real τ-conjecture
According to the real \tau-conjecture, the number of real roots of a sum of products of sparse polynomials should be polynomially bounded in the size of such an expression. It is known that this conjecture implies a superpolynomial lower bound on the arithmetic circuit complexity of the permanent. In this paper, we use the Wronksian determinant to give an upper bound on the number of real roots of sums of products of sparse polynomials. The proof technique is quite versatile; it can in particular be applied to some sparse geometric problems that do not originate from arithmetic circuit complexity. The paper should therefore be of interest to researchers from these two communities (complexity theory and sparse polynomial systems).
Open AccessA Wronskian Approach to the real τ-conjecture
According to the real \tau-conjecture, the number of real roots of a sum of products of sparse polynomials should be polynomially bounded in the size of such an expression. It is known that this conjecture implies a superpolynomial lower bound on the arithmetic circuit complexity of the permanent. In this paper, we use the Wronksian determinant to give an upper bound on the number of real roots of sums of products of sparse polynomials. The proof technique is quite versatile; it can in particular be applied to some sparse geometric problems that do not originate from arithmetic circuit complexity. The paper should therefore be of interest to researchers from these two communities (complexity theory and sparse polynomial systems).
- 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.
- 31 July 2011
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 77 (4) , 820-833
The set of realizations of a max-plus linear sequence is semi-polyhedral
- 31 July 2011
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 77 (4) , 820-833
The set of realizations of a max-plus linear sequence is semi-polyhedral
- Open Access
The set of realizations of a max-plus linear sequence is semi-polyhedral
We show that the set of realizations of a given dimension of a max-plus linear sequence is a finite union of polyhedral sets, which can be computed from any realization of the sequence. This yields an (expensive) algorithm to solve the max-plus minimal realization problem. These results are derived from general facts on rational expressions over idempotent commutative semirings: we show more generally that the set of values of the coefficients of a commutative rational expression in one letter that yield a given max-plus linear sequence is a semi-algebraic set in the max-plus sense. In particular, it is a finite union of polyhedral sets.
Open AccessThe set of realizations of a max-plus linear sequence is semi-polyhedral
We show that the set of realizations of a given dimension of a max-plus linear sequence is a finite union of polyhedral sets, which can be computed from any realization of the sequence. This yields an (expensive) algorithm to solve the max-plus minimal realization problem. These results are derived from general facts on rational expressions over idempotent commutative semirings: we show more generally that the set of values of the coefficients of a commutative rational expression in one letter that yield a given max-plus linear sequence is a semi-algebraic set in the max-plus sense. In particular, it is a finite union of polyhedral sets.
- 21 June 2007
- Published by Elsevier in Theoretical Computer Science
- Vol. 380 (1-2) , 115-126
The quantum query complexity of the abelian hidden subgroup problem
- 21 June 2007
- Published by Elsevier in Theoretical Computer Science
- Vol. 380 (1-2) , 115-126
The quantum query complexity of the abelian hidden subgroup problem
- Open Access
Decidable and undecidable problems about quantum automata
We study the following decision problem: is the language recognized by a quantum finite automaton empty or non-empty? We prove that this problem is decidable or undecidable depending on whether recognition is defined by strict or non-strict thresholds. This result is in contrast with the corresponding situation for probabilistic finite automata for which it is known that strict and non-strict thresholds both lead to undecidable problems.
Open AccessDecidable and undecidable problems about quantum automata
We study the following decision problem: is the language recognized by a quantum finite automaton empty or non-empty? We prove that this problem is decidable or undecidable depending on whether recognition is defined by strict or non-strict thresholds. This result is in contrast with the corresponding situation for probabilistic finite automata for which it is known that strict and non-strict thresholds both lead to undecidable problems.
- 20 December 2001
- Published by Elsevier in Comptes Rendus de l'Académie des Sciences - Series I - Mathematics
- Vol. 333 (12) , 1127-1130
Le problème de la réalisation minimale dans le demi-anneau max-plus et le problème de Pisot sont NP-durs
- 20 December 2001
- Published by Elsevier in Comptes Rendus de l'Académie des Sciences - Series I - Mathematics
- Vol. 333 (12) , 1127-1130
Le problème de la réalisation minimale dans le demi-anneau max-plus et le problème de Pisot sont NP-durs