my publication page on arXiv
Book
[1] Physique quantique, information et calcul – Des concepts aux applications
Pascal Degiovanni, Natacha Portier, Clément Cabart, Alexandre Feller et Benjamin Roussel
EDP Sciences – CNRS ÉDITIONS – Collection : Savoirs Actuels – janvier 2020
International journals
[16] Computing the multilinear factors of lacunary polynomials without heights
Arkadev Chattopadhyay, Bruno Grenet, Pascal Koiran, Natacha Portier and Yann Strozecki
Journal of Symbolic Computation
Volume 104, May–June 2021, Pages 183-206
preprint: http://arxiv.org/abs/1311.5694
long version of our ISSAC 2013 paper Factoring bivariate lacunary polynomials without heights
[15] A Wronskian approach to the real-tau conjecture
Pascal Koiran, Natacha Portier and Sébastien Tavenas
MEGA 2013 special issue of the Journal of Symbolic Computation: Effective Methods in Algebraic Geometry, Volume 68, Part 2, May-June 2015, Pages 195-214 (here and here)
doi: 10.1016/j.jsc.2014.09.036
preprint: http://arxiv.org/abs/1205.1015
[14] On the intersection of a sparse curve and a low-degree curve: A polynomial version of the lost theorem
Pascal Koiran, Natacha Portier and Sébastien Tavenas
preprint: http://arxiv.org/abs/1310.2447
doi 10.1007/s00454-014-9642-1
Discrete & Computational Geometry, January 2015, Volume 53, Issue 1, pp 48-63 (here)
[13] A tau conjecture for Newton polygons
Pascal Koiran, Natacha Portier, Sébastien Tavenas and Stéphan Thomassé
special issue of Foundations of Computational Mathematics celebrating Mike Shub’s 70th birthday, 23 October 2014 (here)
doi 10.1007/s10208-014-9216-x
preprint on arXiv
[12] On the Complexity of the Multivariate Resultant
Bruno Grenet, Pascal Koiran and Natacha Portier
Journal of Complexity, 29(2), p. 142-157, 2013http://dx.doi.org/10.1016/j.jco.2012.10.001
Part of the material was previously published in our MFCS 2010 paper The multivariate resultant is NP-hard in any characteristic
[11] The Set of Realizations of a Max-plus Linear Sequence is Semi-polyhedral
Vincent Blondel, Natacha Portier and Stéphane Gaubert.
Journal of Computer and System Sciences (JCSS), Volume 77, Issue 4, July 2011, Pages 820-833
http://dx.doi.org/10.1016/j.jcss.2010.08.010
caml implementation (Guillaume Melquiond and Pierre Philipps) can be found here
[10] Adversary lower bounds for nonadaptive quantum algorithms
Pascal Koiran, Jürgen Landes, Natacha Portier, Penghui Yao,
Journal of Computer and System Sciences 76 (2010), pp. 347-355 (JCSS special issue on Wollic’08)
http://dx.doi.org/10.1016/j.jcss.2009.10.007
[9] Characterizing Valiant’s algebraic complexity classes
Guillaume Malod and Natacha Portier
Journal of complexity, Volume 24, Issue 1, February 2008
LIP Research Report 2005-44 : get it
[8] The quantum query complexity of the Abelian Subgroup Problem
Pascal Koiran, Vincent Nesme and Natacha Portier
Theoretical Computer Science, Volume 380, Numbers 1-2, June 2007, pp. 115-126
preprint is here
[7] Decidable and undecidable problems about quantum automata
with Vincent Blondel , Emmanuel Jeandel, Pascal Koiran and Natacha Portier
SIAM Journal on Computing 2005, Volume 34, Number 6, pp. 1464-1473 : here
LIP Research Report 2003-24, and preprint quant-ph/0304082 : get here
[6] A Rank Theorem for Vandermonde Matrices
With Pascal Koiran, Natacha Portier and Gilles Villard
Linear Algebra and its Applications, Volume 378, 1 February 2004, Pages 99-107
LIP Research Report 2001-34 du LIP (get it) extended: new file
[5] The presence of a zero in an integer linear recurrent sequence is NP-hard to decide
Vincent Blondel and Natacha Portier
Linear Algebra and its Applications, Volumes 351-352, 15 August 2002, Pages 91-98
LIP Research Report 1999-47: get it
[4] Back-and-forth systems for generic curves and a decision algorithm for the limit theory
Annals of Pure and Applied Logic 111 (2001) 257-275
Pascal Koiran and Natacha Portier
LIP Research Report 2000-29: get it
French short version: Un algorithme de décision pour la limite des théories de courbes génériques.
Proceedings of the fifth franco-kasak model theory colloquium, Qaragandy, June 2000.
LIP Research Report 2000-27: get it
[3] Le problème des grandes puissances et celui des grandes racines.
(The problem of large powers and the one of large roots)
Natacha Portier
Journal of Symbolic Logic Vol. 65, Number 4, December 2000, pp. 1675-1685.
To read the abstract (résumé) .
get the pdf
[2] Stabilité polynômiale des corps différentiels.
(Polynomial Stability of Differential Fields)
Natacha Portier
Journal of Symbolic Logic Vol. 64, Number 2, June 1999, pp. 803-816
To read the abstract (résumé) .
get the pdf
[1] Résolutions universelles pour des problèmes NP-complets.
(Universal Relations for NP-complete problems)
Natacha Portier
Theoretical Computer Science (201)1-2 (1998) pp. 137-150.
To read the abstract (résumé) .
get the pdf
Book Chapter
[1] Symmetric Determinantal Representation of Formulas and Weakly Skew Circuits
Bruno Grenet, Erich Kaltofen, Pascal Koiran and Natacha Portier
Randomization, Relaxation, and Complexity in Polynomial Equation Solving, Contemporary Mathematics (AMS), Volume 556, November 2011, pp 61-96
http://dx.doi.org/10.1090/conm/556 (volume)
long version of STACS2011 Symmetric Determinantal Representation of Weakly Skew Circuits
the preprint is here
International Conferences
[9] Factoring bivariate lacunary polynomials without heights
Arkadev Chattopadhyay, Bruno Grenet, Pascal Koiran, Natacha Portier and Yann Strozecki
ISSAC 2013
preprint: http://arxiv.org/abs/1206.4224
[8] A Wronskian approach to the real-tau conjecture
Pascal Koiran, Natacha Portier and Sébastien Tavenas
MEGA 2013 (no proceedings for this conference but the paper is accepted in the special issue of the Journal of Symbolic Computation on Effective Methods in Algebraic Geometry)
preprint: http://arxiv.org/abs/1205.1015
[7] The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent
Bruno Grenet, Pascal Koiran, Natacha Portier and Yann Strozecki,
FSTTCS 2011 (IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, December 12 to 14, 2011, IIT Bombay, Mumbai, India)
DOI 10.4230/LIPIcs.FSTTCS.2011.127
preprint
[6] Symmetric Determinantal Representation of Weakly Skew Circuits
Bruno Grenet, Erich Kaltofen, Pascal Koiran and Natacha Portier
STACS 2011 (28th International Symposyium on Theoretical Aspects of Computer Science)
DOI : 10.4230/LIPIcs.STACS.2011.543
for the long version see the Research Report
[5] The multivariate resultant is NP-hard in any characteristic
Bruno Grenet, Pascal Koiran and Natacha Portier
MFCS 2010 (35th International Symposium on Mathematical Foundations of Computer Science)
DOI http://dx.doi.org/10.1007/978-3-642-15155-2_42
extended preprint here
[4] Adversary lower bounds for nonadaptive quantum algorithms
Pascal Koiran, Jürgen Landes, Natacha Portier and Penghui Yao,
WOLLIC 2008 ( 15th Workshop on Logic, Language, Information and Computation)
preprint here
[3] Characterizing Valiant’s algebraic complexity classes
Guillaume Malod and Natacha Portier
MFCS 2006, link to the LNCS paper
LIP Research Report 2005-44 : get it
[2]A quantum lower bound for the query complexity of Simon’s problem
Pascal Koiran, Vincent Nesme and Natacha PortierICALP 2005
preprint is here
with added results here
[1] The Set of Realizations of a Max-plus Linear Sequence is Semi-polyhedral
Vincent Blondel, Stéphane Gaubert and Natacha Portier
Conference on Advances in Communications and Control, ComCon 8 (Crete, 25-29 June 2001)
CRAS
[1] Le problème de la réalisation minimale dans le demi-anneau max-plus et le problème de Pisot sont NP-durs
Vincent Blondel and Natacha Portier, in Comptes Rendus de l’Académie des Sciences-Série I/Mathématiques- Series I – Mathematics, 333 (12) (2001) pp. 1127-1130
Others
[6] Counting tropically degenarate valuations and p-adic approaches to the hardness of the permanent
Pascal Koiran, Natacha Portier and J. Maurice Rojas
preprint: http://arxiv.org/abs/1309.0486
submitted
[5] On the probabilistic query complexity of transitively symmetric problems.
Pascal Koiran, Vincent Nesme and Natacha Portier
Research Report[4] The minimal realization problem in max-plus algebra is NP-hard
Vincent Blondel and Natacha Portier, Notes de lectures des Journées thématiques Algèbres tropicales-ALAPEDES, ENS, 29-31 mars 1999[3] Le problème des grandes puissances et celui des grandes racines : une introduction à la complexité sur les corps et les corps différentiels.
Natacha Portier
4 pages text for non-specialists.
femmes et math (proceedings of the fourth French Young Mathematician Women Forum , february 1999)[2] Résolutions universelles pour des problèmes NP-complets (Introduction).
Natacha Portier
4 pages text for non-specialists.
femmes et math (women and mathematics, proceedings of the second French Young Mathematician Women Forum, January 31, 1997), supplément au numéro 3, Janvier 1999
[1] Complexité algébrique : Stabilité polynômiale des corps différentiels & Résolutions universelles pour des problèmes NP-complets.
Natacha Portier
Ph. D. Thesis defended on 9th of Decembre, 1998 at University Lyon I. (For title, jury and abstract click here).
Get the ps file here.