Natacha Portier

According to our database, Natacha Portier authored at least 25 papers between 1998 and 2021.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2021

Computing the multilinear factors of lacunary polynomials without heights.

Arkadev Chattopadhyay, Bruno Grenet, Pascal Koiran, Natacha Portier, Yann Strozecki

J. Symb. Comput., 2021

2015

A Wronskian approach to the real τ-conjecture.

Pascal Koiran, Natacha Portier, Sébastien Tavenas

J. Symb. Comput., 2015

A $$\tau $$ τ -Conjecture for Newton Polygons.

Pascal Koiran, Natacha Portier, Sébastien Tavenas, Stéphan Thomassé

Found. Comput. Math., 2015

On the Intersection of a Sparse Curve and a Low-Degree Curve: A Polynomial Version of the Lost Theorem.

Pascal Koiran, Natacha Portier, Sébastien Tavenas

Discret. Comput. Geom., 2015

2013

On the complexity of the multivariate resultant.

Bruno Grenet, Pascal Koiran, Natacha Portier

J. Complex., 2013

A tau-conjecture for Newton polygons.

Pascal Koiran, Natacha Portier, Sébastien Tavenas, Stéphan Thomassé

CoRR, 2013

Counting Tropically Degenerate Valuations and p-adic Approaches to the Hardness of the Permanent.

Pascal Koiran, Natacha Portier, J. Maurice Rojas

CoRR, 2013

Author Index.

Natacha Portier, Thomas Wilke

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Frontmatter, Table of Contents, Preface, Workshop Organization.

Natacha Portier, Thomas Wilke

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Factoring bivariate lacunary polynomials without heights.

Arkadev Chattopadhyay, Bruno Grenet, Pascal Koiran, Natacha Portier, Yann Strozecki

Proceedings of the International Symposium on Symbolic and Algebraic Computation, 2013

2011

The set of realizations of a max-plus linear sequence is semi-polyhedral.

Vincent D. Blondel, Stéphane Gaubert, Natacha Portier

J. Comput. Syst. Sci., 2011

Symmetric Determinantal Representation of Weakly-Skew Circuits.

Bruno Grenet, Erich L. Kaltofen, Pascal Koiran, Natacha Portier

Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent.

Bruno Grenet, Pascal Koiran, Natacha Portier, Yann Strozecki

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

2010

Adversary lower bounds for nonadaptive quantum algorithms.

Pascal Koiran, Jürgen Landes, Natacha Portier, Penghui Yao

J. Comput. Syst. Sci., 2010

Symmetric Determinantal Representation of Formulas and Weakly Skew Circuits

Bruno Grenet, Erich L. Kaltofen, Pascal Koiran, Natacha Portier

CoRR, 2010

The Multivariate Resultant Is NP-hard in Any Characteristic.

Bruno Grenet, Pascal Koiran, Natacha Portier

Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

2009

The multivariate resultant lies between NP and AM

Bruno Grenet, Pascal Koiran, Natacha Portier

CoRR, 2009

2008

Characterizing Valiant's algebraic complexity classes.

Guillaume Malod, Natacha Portier

J. Complex., 2008

2007

The quantum query complexity of the abelian hidden subgroup problem.

Pascal Koiran, Vincent Nesme, Natacha Portier

Theor. Comput. Sci., 2007

2005

Decidable and Undecidable Problems about Quantum Automata.

Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, Natacha Portier

SIAM J. Comput., 2005

A Quantum Lower Bound for the Query Complexity of Simon's Problem.

Pascal Koiran, Vincent Nesme, Natacha Portier

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

2001

Back-and-forth systems for generic curves and a decision algorithm for the limit theory.

Pascal Koiran, Natacha Portier

Ann. Pure Appl. Log., 2001

2000

Le Problème des Grandes Puissances Et Celui des Grandes Racines.

Natacha Portier

J. Symb. Log., 2000

1999

Stabilité Polynômiale des Corps Différentiels.

Natacha Portier

J. Symb. Log., 1999

1998

Résolutions universelles pour des problèmes NP-complets.

Natacha Portier

Theor. Comput. Sci., 1998