{"id":12,"date":"2020-09-22T15:21:30","date_gmt":"2020-09-22T13:21:30","guid":{"rendered":"http:\/\/perso.ens-lyon.fr\/natacha.portier\/blog\/?page_id=12"},"modified":"2022-03-30T16:19:18","modified_gmt":"2022-03-30T14:19:18","slug":"publications","status":"publish","type":"page","link":"https:\/\/perso.ens-lyon.fr\/natacha.portier\/blog\/publications\/","title":{"rendered":"Publications"},"content":{"rendered":"\n

my publication page on arXiv<\/a><\/p>\n\n\n\n

Book<\/h2>\n\n\n\n

[1] Physique quantique, information et calcul – Des concepts aux applications<\/strong>
Pascal Degiovanni, Natacha Portier, Cl\u00e9ment Cabart, Alexandre Feller et Benjamin Roussel
EDP Sciences – CNRS \u00c9DITIONS – Collection : Savoirs Actuels – janvier 2020<\/p>\n\n\n\n

International journals<\/h2>\n\n\n\n

[16] Computing the multilinear factors of lacunary polynomials without heights
<\/strong>Arkadev Chattopadhyay,\u00a0Bruno Grenet<\/a>,\u00a0Pascal Koiran<\/a>, Natacha Portier and Yann Strozecki
Journal of Symbolic Computation<\/a>
Volume 104<\/a>,\u00a0May\u2013June 2021, Pages 183-206
preprint:\u00a0http:\/\/arxiv.org\/abs\/1311.5694<\/a>
long version of our ISSAC 2013 paper Factoring bivariate lacunary polynomials without heights<\/p>\n\n\n\n

[<\/strong>15] A Wronskian approach to the real-tau conjecture<\/strong>
Pascal Koiran<\/a>, Natacha Portier and S\u00e9bastien Tavenas
MEGA 2013<\/a> special issue of the Journal of Symbolic Computation: Effective Methods in Algebraic Geometry, Volume 68, Part 2, May-June 2015, Pages 195-214 (here<\/a> and here<\/a>)
doi: 10.1016\/j.jsc.2014.09.036
preprint: http:\/\/arxiv.org\/abs\/1205.1015<\/a><\/p>\n\n\n\n

[14] On the intersection of a sparse curve and a low-degree curve: A polynomial version of the lost theorem<\/strong>
Pascal Koiran, Natacha Portier and S\u00e9bastien Tavenas
preprint: http:\/\/arxiv.org\/abs\/1310.2447<\/a>
doi 10.1007\/s00454-014-9642-1
Discrete & Computational Geometry<\/a>, January 2015, Volume 53, Issue 1, pp 48-63 (here<\/a>)<\/p>\n\n\n\n

[13] A tau conjecture for Newton polygons
<\/strong>Pascal Koiran, Natacha Portier, S\u00e9bastien Tavenas and St\u00e9phan Thomass\u00e9
special issue of Foundations of Computational Mathematics<\/a> celebrating Mike Shub’s 70th birthday, 23 October 2014 (here<\/a>)
doi 10.1007\/s10208-014-9216-x
preprint on arXiv<\/a><\/p>\n\n\n\n

[12] On the Complexity of the Multivariate Resultant<\/strong>
Bruno Grenet<\/a>, Pascal Koiran<\/a> and Natacha Portier
Journal of Complexity, <\/em>29(2), p. 142-157, 2013http:\/\/dx.doi.org\/10.1016\/j.jco.2012.10.001<\/a>
Part of the material was previously published in our MFCS 2010 paper The multivariate resultant is NP-hard in any characteristic<\/em><\/p>\n\n\n\n

[11] The Set of Realizations of a Max-plus Linear Sequence is Semi-polyhedral<\/strong>
Vincent Blondel<\/a>, Natacha Portier and St\u00e9phane Gaubert<\/a>.
Journal of Computer and System Sciences<\/em> (JCSS)<\/a>, Volume 77, Issue 4, July 2011, Pages 820-833
http:\/\/dx.doi.org\/10.1016\/j.jcss.2010.08.010<\/u><\/a>
caml implementation (Guillaume Melquiond and Pierre Philipps) can be found here<\/a>

[10] Adversary lower bounds for nonadaptive quantum algorithms<\/strong>
Pascal Koiran<\/a>, J\u00fcrgen Landes, Natacha Portier, Penghui Yao<\/a>,
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<\/a>

[9] Characterizing Valiant’s algebraic complexity classes<\/strong>
Guillaume Malod<\/a> and Natacha Portier
Journal of complexity<\/a>, Volume 24, Issue 1, February 2008
LIP Research Report 2005-44  : get it<\/a>
<\/strong>
[8] The quantum query complexity of the Abelian Subgroup Problem<\/strong>
Pascal Koiran<\/a>, Vincent Nesme<\/a> and Natacha Portier
Theoretical Computer Science<\/a>, Volume 380, Numbers 1-2, June 2007, pp. 115-126
preprint is here<\/a>

[7] Decidable and undecidable problems about quantum automata<\/strong>
with Vincent Blondel<\/a> , Emmanuel Jeandel<\/a>, Pascal Koiran<\/a> and Natacha Portier
SIAM Journal on Computing<\/a> 2005, Volume 34, Number 6, pp. 1464-1473 : here<\/a>
LIP Research Report 2003-24,  and preprint quant-ph\/0304082 : get here<\/a> 

[6] A Rank Theorem for Vandermonde Matrices<\/strong>
With Pascal Koiran<\/a>, Natacha Portier and Gilles Villard<\/a>
Linear Algebra and its Applications<\/a>, Volume 378, 1 February 2004, Pages 99-107<\/em>
LIP Research Report 2001-34 du LIP (get it<\/a>) extended: new file<\/a>

[5] The presence of a zero in an integer linear recurrent sequence is NP-hard to decide<\/strong>
Vincent Blondel<\/a> and Natacha Portier
Linear Algebra and its Applications<\/a>, Volumes 351-352, 15 August 2002, Pages 91-98<\/em>
LIP Research Report 1999-47: get it<\/a>

[4] Back-and-forth systems for generic curves and a decision algorithm for the limit theory<\/strong>
Annals of Pure and Applied Logic 111 (2001) 257-275<\/em>
Pascal Koiran<\/a> and Natacha Portier
LIP Research Report 2000-29: get it<\/a>
French short version: Un algorithme de d\u00e9cision pour la limite des th\u00e9ories de courbes g\u00e9n\u00e9riques<\/strong>.
Proceedings of the fifth franco-kasak model theory colloquium, Qaragandy, June 2000.
LIP Research Report 2000-27: get it<\/a>

[3] Le probl\u00e8me des grandes puissances et celui des grandes racines.<\/strong>
(The problem of large powers and the one of large roots)
Natacha Portier
Journal of Symbolic Logic<\/a> Vol. 65, Number 4, December 2000, pp. 1675-1685.<\/em>
To read the abstract (r\u00e9sum\u00e9) <\/a>.
get the pdf<\/a><\/em>

[2] Stabilit\u00e9 polyn\u00f4miale des corps diff\u00e9rentiels.<\/strong>
(Polynomial Stability of Differential Fields)
Natacha Portier
Journal of Symbolic Logic<\/a> Vol. 64, Number 2, June 1999, pp. 803-816<\/em>
To read the abstract (r\u00e9sum\u00e9) <\/a>.
get the pdf<\/a><\/em>

[1] R\u00e9solutions universelles pour des probl\u00e8mes NP-complets.<\/strong> 
(Universal Relations for NP-complete problems)
Natacha Portier
Theoretical Computer Science <\/a>(201)1-2 (1998) pp. 137-150.
To read the abstract (r\u00e9sum\u00e9) <\/a>.
get the <\/em>pdf<\/a><\/p>\n\n\n\n

Book Chapter<\/h2>\n\n\n\n

[1] Symmetric Determinantal Representation of Formulas and Weakly Skew Circuits<\/strong>
Bruno Grenet<\/a>, Erich Kaltofen<\/a>, Pascal Koiran<\/a> and Natacha Portier
Randomization, Relaxation, and Complexity in Polynomial Equation Solving,<\/em> Contemporary Mathematics (AMS), Volume 556<\/a>, November 2011, pp 61-96
http:\/\/dx.doi.org\/10.1090\/conm\/556<\/a> (volume)
long version of STACS2011 Symmetric Determinantal Representation of Weakly Skew Circuits
the preprint is here<\/a><\/p>\n\n\n\n

International Conferences<\/h2>\n\n\n\n

[9] Factoring bivariate lacunary polynomials without heights
<\/strong>Arkadev Chattopadhyay, Bruno Grenet<\/a>, Pascal Koiran<\/a>, Natacha Portier and Yann Strozecki
ISSAC 2013<\/a>
preprint: http:\/\/arxiv.org\/abs\/1206.4224<\/a><\/p>\n\n\n\n

[8] A Wronskian approach to the real-tau conjecture<\/strong>
Pascal Koiran<\/a>, Natacha Portier and S\u00e9bastien Tavenas
MEGA 2013<\/a> (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<\/a><\/p>\n\n\n\n

[7] The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent
<\/strong>Bruno<\/a> Grenet<\/a>, Pascal Koiran<\/a>, Natacha Portier and Yann Strozecki<\/a>,
FSTTCS 2011<\/a> (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<\/a><\/p>\n\n\n\n

[6] Symmetric Determinantal Representation of Weakly Skew Circuits<\/strong>
Bruno Grenet<\/a>, Erich Kaltofen<\/a>, Pascal Koiran<\/a> and Natacha Portier
STACS 2011 (28th International Symposyium on Theoretical Aspects of Computer Science)
DOI : 10.4230\/LIPIcs.STACS.2011.543<\/a>
for the long version see the Research Report<\/a><\/p>\n\n\n\n

[5] The multivariate resultant is NP-hard in any characteristic
<\/strong>Bruno Grenet<\/a>, Pascal Koiran<\/a> 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<\/a>

[4] Adversary lower bounds for nonadaptive quantum algorithms
<\/strong>Pascal Koiran<\/a>, J\u00fcrgen Landes, Natacha Portier and Penghui Yao,
WOLLIC 2008<\/a> ( 15th Workshop on Logic, Language, Information and Computation)
preprint here<\/a>

[3] Characterizing Valiant’s algebraic complexity classes<\/strong>
Guillaume Malod<\/a> and Natacha Portier
MFCS 2006<\/a>, link to the LNCS paper<\/a>
LIP Research Report 2005-44 : get it<\/a>

[2]A quantum lower bound for the query complexity of Simon’s problem<\/strong>
Pascal Koiran<\/a>, Vincent Nesme<\/a> and Natacha PortierICALP 2005
preprint is here<\/a>
with added results here<\/a>

[1] The Set of Realizations of a Max-plus Linear Sequence is Semi-polyhedral<\/strong>
Vincent Blondel<\/a>, St\u00e9phane Gaubert<\/a> and Natacha Portier
Conference on Advances in Communications and Control, ComCon 8 (Crete, 25-29 June 2001)<\/p>\n\n\n\n

CRAS<\/strong><\/h2>\n\n\n\n

[1] Le probl\u00e8me de la r\u00e9alisation minimale dans le demi-anneau max-plus et le probl\u00e8me de Pisot sont NP-durs<\/strong>
Vincent Blondel<\/a> and Natacha Portier,  in Comptes Rendus de l’Acad\u00e9mie des Sciences-S\u00e9rie I\/Math\u00e9matiques- Series I – Mathematics, 333 (12) (2001) pp. 1127-1130
 
 <\/p>\n\n\n\n

Others<\/h2>\n\n\n\n

[6] Counting tropically degenarate valuations and p-adic approaches to the hardness of the permanent
<\/strong>Pascal Koiran, Natacha Portier and J. Maurice Rojas
preprint: http:\/\/arxiv.org\/abs\/1309.0486<\/a>
submitted<\/p>\n\n\n\n

[5] On the probabilistic query complexity of transitively symmetric problems.
<\/strong>Pascal Koiran<\/a>, Vincent Nesme<\/a> and Natacha Portier
Research Report<\/a>[4] The minimal realization problem in max-plus algebra is NP-hard
<\/strong>Vincent Blondel<\/a> and Natacha Portier, Notes de lectures des Journ\u00e9es th\u00e9matiques Alg\u00e8bres tropicales-ALAPEDES, ENS, 29-31 mars 1999[3] Le probl\u00e8me des grandes puissances et celui des grandes racines : une introduction \u00e0 la complexit\u00e9 sur les corps et les corps diff\u00e9rentiels.
<\/strong>Natacha Portier
4 pages text for non-specialists.
femmes et math <\/em>(proceedings of the fourth French Young Mathematician Women Forum , february 1999)[2] R\u00e9solutions universelles pour des probl\u00e8mes NP-complets (Introduction).
<\/strong>Natacha Portier
4 pages text for non-specialists.
femmes et math <\/em>(women and mathematics, proceedings of the second French Young Mathematician Women Forum, January 31, 1997), suppl\u00e9ment au num\u00e9ro 3, Janvier 1999<\/p>\n\n\n\n

[1] Complexit\u00e9 alg\u00e9brique : Stabilit\u00e9 polyn\u00f4miale des corps diff\u00e9rentiels & R\u00e9solutions universelles pour des probl\u00e8mes NP-complets.
<\/strong>Natacha Portier
Ph. D. Thesis defended on 9th of Decembre, 1998 at University Lyon I. (For title, jury and abstract click here<\/a>).
Get the ps file here<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"

my publication page on arXiv Book [1] Physique quantique, information et calcul – Des concepts aux applicationsPascal Degiovanni, Natacha Portier, Cl\u00e9ment Cabart, Alexandre Feller et Benjamin RousselEDP Sciences – CNRS \u00c9DITIONS – Collection : Savoirs Actuels – janvier 2020 International journals [16] Computing the multilinear factors of lacunary polynomials without heightsArkadev Chattopadhyay,\u00a0Bruno Grenet,\u00a0Pascal Koiran, Natacha Portier […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"templates\/template-cover.php","meta":{"footnotes":""},"class_list":["post-12","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/perso.ens-lyon.fr\/natacha.portier\/blog\/wp-json\/wp\/v2\/pages\/12","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/perso.ens-lyon.fr\/natacha.portier\/blog\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/perso.ens-lyon.fr\/natacha.portier\/blog\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/perso.ens-lyon.fr\/natacha.portier\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/perso.ens-lyon.fr\/natacha.portier\/blog\/wp-json\/wp\/v2\/comments?post=12"}],"version-history":[{"count":14,"href":"https:\/\/perso.ens-lyon.fr\/natacha.portier\/blog\/wp-json\/wp\/v2\/pages\/12\/revisions"}],"predecessor-version":[{"id":137,"href":"https:\/\/perso.ens-lyon.fr\/natacha.portier\/blog\/wp-json\/wp\/v2\/pages\/12\/revisions\/137"}],"wp:attachment":[{"href":"https:\/\/perso.ens-lyon.fr\/natacha.portier\/blog\/wp-json\/wp\/v2\/media?parent=12"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}