[12] Symmetric Determinantal Representation of Formulas and
Weakly Skew Circuits
Bruno
Grenet, Erich Kaltofen,
Pascal Koiran
and Natacha Portier
to appear in AMS Contemporary Mathematics
Proceedings
long version of STACS2011 Symmetric
Determinantal Representation of Weakly Skew Circuits
the
preprint is here
[11] The Set of Realizations of a Max-plus Linear Sequence is
Semi-polyhedral
Vincent
Blondel, Natacha Potier and Stéphane
Gaubert.
Journal
of Computer and System Sciences (JCSS), Volume 77, Issue 4,
July 2011, Pages 820-833
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
LIP Research Report 2005-44 :
get
it
Journal
of complexity,
Volume 24, Issue 1, February 2008
[8]
The quantum query complexity of the Abelian Subgroup
Problem
Pascal
Koiran, Vincent
Nesme and Natacha Portier
preprint is here
Theoretical
Computer Science, Volume 380, Numbers 1-2, June 2007, pp.
115-126
[7] Decidable and undecidable problems about
quantum automata
with Vincent
Blondel , Emmanuel
Jeandel, Pascal
Koiran and Natacha Portier
LIP Research Report 2003-24,
and preprint quant-ph/0304082 : get here
SIAM
Journal on Computing 2005, Volume 34, Number 6, pp. 1464-1473 :
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
[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)
preprint
[6] Symmetric Determinantal Representation of Weakly Skew
Circuits
Bruno
Grenet, Erich Kaltofen,
Pascal Koiran
and Natacha Portier
STACS
2011
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)
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
LIP Research Report 2005-44 : get
it
MFCS 2006, link
to the LNCS paper
[2]A quantum lower bound for the
query complexity of Simon's problem
Pascal
Koiran, Vincent
Nesme and Natacha Portier
preprint is here
ICALP
2005
with addPascal
Koiraned 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)
[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
[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.
Back to Natacha Portier homepage
Last modification on July 2011