IRMAR, CNRS URM 6625,
Université de Rennes I,
Rennes, France.
Research Interests : algorithmes de la géométrie algébrique réelle
Marie-Françoise Roy's field of research is real algebraic geometry. She worked first on the theory of the real spectrum, and more recently on the complexity of algorithmic problems in real algebraic geometry.
She was one of the founders, in 1987, of the French association for women in mathematics, " Femmes et mathématiques ".
Selected Publications : Ouvrages
S. Basu, R. Pollack, M.-F. Roy. Algorithms in real algebraic geometry. Berlin Heidelberg New York: Springer 2003.
J. Bochnak , M. Coste , M.-F. Roy. Real algebraic geometry. Second edition in english.Ergebnisse der Mat., vol. 36. Berlin Heidelberg New York: Springer 1998.
J. Bochnak , M. Coste , M.-F. Roy. Géométrie Algébrique Réelle. Ergebnisse der Mat., vol. 12. Berlin Heidelberg New York: 1987.
Articles
M. Coste, T. Lajous, H. Lombardi, M.-F. Roy. Generalized Budan-Fourier theorem and virtual roots. A paraitre au Journal of Complexity.
S. Basu, R. Pollack, M.-F. Roy. Computing the dimension of a semi-algebraic set. Zap.Nauchn. Sem. POMI 316 (2004)
S. Basu, R. Pollack, M.-F. Roy. Computing the Euler-Poincare characteristic of sign conditions., Journal of computational complexity. Sous presse.
S. Basu, R. Pollack, M.-F. Roy. On the Betti numbers of Sign Conditions. Proceedings of the AMS. Sous presse.
M.-F. Roy , N. Vorobjov. Computing the complexification of a semi-algebraic set, Math. Zeitschrift 239, 131-142 (2002)
T. Lickteig, M.-F. Roy. Sylvester-Habicht sequences and fast Cauchy index computations, Journal of Symbolic Computation, , 31 315-341 (2001)
M. Coste, H. Lombardi, M.-F. Roy. Dynamical method in algebra: effective Nullstellensatze, Annals of Pure and Applied Logic, 111, 203-256 (2001)
H. Lombardi , M.-F. Roy, M. Safey. New structure theorems for subresultants, Special Issue Symbolic Computation in Algebra, Analysis, and Geometry, Journal of Symbolic Computation, 29 663-690 (2000)
F. Rouillier, M.-F. Roy, M. Safey. Finding at least one point in each connected component of a real algebraic set defined by a single equation, Journal of Complexity 16 716-750 (2000)
S. Basu, R. Pollack, M.-F. Roy. Computing roadmaps of semi-algebraic sets on a variety,Journal of the AMS, VOL 3, 1 55-82 (1999)
S. Basu, R. Pollack, M.-F. Roy. On Computing a Set of Points meeting every Cell Defined by a Family of Polynomials on a Variety, Journal of Complexity, 13 28-37 (1997)
T. Lickteig, M.-F. Roy. Semi-algebraic complexity of quotients and sign determinations of remanders , Journal of Complexity 12 (4) 545-571 (1996)
I. Itenberg, M.-F. Roy. Multivariate Descartes's rule Beitrage zur Algebra und Geometrie Volume 37 (1996) 2, 337-346
S. Basu, R. Pollack, M.-F. Roy. On the combinatorial and algebraic complexity of Quantifier elimination, J. A. C. M., 43, 1002--1045, (1996).
H. Lombardi, N. Mnev M.-F. Roy. The Positivstellensatz and small deduction rules for systems of inequalities, Math. Nachr. 181 245-2259 (1996).
S. Basu, R. Pollack M.-F. Roy. On the number of cells defined by a family of polynomials on a subvariety, Mathematika 43 120-126 (1996).
M.-F. Roy, N.N.Vorobjov. Finding irreducible components of some real transcendental varieties. Journal of Computationnal complexity 4 107-132 (1994)
J. Heintz, M.-F. Roy, P. Solerno. On the theoretical and practical complexity of the existential theory of the reals. The Computer Journal, vol 36, 5 427-431(1993).
J. Heintz, M.-F. Roy, P. Solerno. Description of the connected components of a semi-algebraic set in single exponential time Discrete and Computationnal Geometry 11 121-140 (1994).
F. Cucker, H. Laneau, B. Mishra, P. Pedersen, M.-F. Roy. NC algorithms for Real algebraic numbers. Applicable Algebra in Engineering, 39
L. Gonzalez, H. Lombardi, T. Recio, M.-F. Roy. Spécialisation de la suite de Sturm. II Informatique théorique et applications 28 1-24 (1994).
J. Heintz, M.-F. Roy P. Solerno. Sur la complexité du principe de Tarski-Seidenberg. Bulletin de la SMF 118 101-126 (1990).
F. Cucker, M.-F. Roy. A theorem on random polynomials and some consequences in average complexity . Journal of Symbolic Computation 10 (1990).
L. Gonzalez, H. Lombardi, T. Recio, M.-F. Roy. Sous-résultants et spécialisation de la suite de Sturm. I I. Informatique théorique et applications 24 561-588 (1990).
M. Coste, M.-F. Roy. Encore une démonstration de l'existence de stratifications avec lacondition w. Bulletin of the Polish Academy of Science 37 597-601 (1989) .
M.-F. Roy, A. Szpirglas. Complexity of the computations with real algebraic numbers. Journal of Symbolic Computation 10 39-51 (1990).
M.-F. Roy. Computation of the topology of a real algebraic curve. Astérisque 192 (1990)17-33.
M. Coste, M.-F. Roy. Thom's lemma, the coding of real algebraic numbers and thetopology of semi-algebraic sets . Journal of Symbolic Computation 5 121-130 (1988)
M. E. Alonso, M.-F. Roy. Real strict localisations. Math. Z. 194, 429-441 (1987)
M. Coste, M.-F. Roy. La topologie du spectre réel. Contemp. Math 8, 27-59 (1982).
M. Coste, M.-F. Roy. Le topos étale réel d'un anneau. Cahiers topologie géom. différentielle, 22, 19-24 (1981)
M. Coste, L. Mahé, M.-F. Roy. Contribution to the study of the natural number object in a topos. J. Pure Appl. Algebra 17, 35-68 (1980)
Thèse
M.-F. Roy. Spectre réel d'un anneau et topos étale réel. Thèse d'état, Université Paris-Nord (1980)
Articles de synthèse
S. Basu, R. Pollack, M.-F. Roy. Betti numbers: bounds, applications and algorithms. MSRI volume "Discrete and computational geometry". Sous presse.
M.-F. Roy, Some recent quantitative and algorithmic results in real algebraic geometry, 737-750, Goodman/Pollack Festschrift, Springer (2003) .
M.-F. Roy, Formes et formules: les algorithmes de la géométrie algébrique réelle, 53-63 dans Calculs et formes : de l'activité mathématique, Jacqueline Boniface ed., Ellipses (2003).
M.-F. Roy, Three problem in real algeraic geometry and their descendants, 991-1002,Mathematics unlimited, 2001 and Beyond, Sprigner Verlag (2001).
M.-F. Roy. Géométrie algébrique réelle, Development of Mathematics 1950-2000 , 939-966, Birkhauser (2000)
I. Itenberg, M.-F. Roy. Interactions between real algebraic geometry and discrete and computational geometry, Advances in Discrete and Computational Geometry, AMS, Contemporary mathematics 223 217-236 (1999)
M.-F. Roy. Basic algorithms in real algebraic geometry: from Sturm theorem to the existential theory of reals, Lectures on Real Geometry in memoriam of Mario Raimondo, de Gruyter Expositions in Mathematics 23, 1-67 (1996)
M.-F. Roy. Computations in Real Algebraic Geometry, Summer Seminar " Mathematics of Numerical Anlysis: Real number algorithms " (Park City 1995), AMS Conference in Applied mathematics. Lectures in Applied Mathematics 32 701-713(1996)
J. Heintz, T. Recio, M.-F. Roy. Algorithms in real algebraic geometry and applications to computational geometry. DIMACS Series in Discrete and Computational Mathematics. AMS 137-163(1991).
L. Gonzalez-Vega, F. Rouillier, M.-F. Roy. Symbolic Recipes for Polynomial System Solving, In: Some tapas of computer algebra, A. Cohen et al. ed. Springer, 34-65 (1999).
L. Gonzalez-Vega, F. Rouillier, M.-F. Roy, G. Trujillo. Symbolic Recipes for Real Solutions In: Some tapas of computer algebra, A. Cohen et al. ed. Springer, 121-167 (1999).
Textes acceptés comme communications à des congrès internationaux
S. Basu R. Pollack M.-F. Roy. Computing connected components of semi-agebraic sets, ISSACC 98
S. Basu R. Pollack M.-F. Roy. Computing Roadmaps of Semi-algebraic Sets on a Variety, Foundations of Computational Mathematics. F. Cucker and M. Shub, Eds., 1--15,1997.
S. Basu R. Pollack M.-F. Roy. Computing Roadmaps of Semi-algebraic Sets, Proc. 28 Annual ACM Symposium on the Theory of Computing, 168-173, 1996.
M.-F. Roy, N. Vorobjov. Computing the complexification of a semi-algebraic set, ISSACC 96 Proceedings 26-39 (1996).
S. Basu R. Pollack M.-F. Roy. On the combinatorial and algebraic complexity of Quantifier elimination, Proc. 11 th IEEE Symp. On Foundations of Computer Science, 1994, 632-641.
S. Basu, R. Pollack, M.-F. Roy. A new algorithm to find a point in every cell defined by a family of polynomials. Quantifier Elimination and Cylrindical Algebraic Decomposition, Texts and Mongraphs in Symbolic Computation, B. Caviness and J. Johnson, Eds. , Springer 341-350 (1998)
L. Gonzalez, H. Lombardi, T. Recio, M.-F. Roy. Sturm-Habicht,determinants and real roots of univariate polynomials. . Quantifier Elimination and Cylrindical Algebraic Decomposition, Texts and Mongraphs in Symbolic Computation, B. Caviness and J. Johnson, Eds. Springer 300-316 (1998)
M.-E. Alonso, E. Becker, M.-F. Roy, T. Wormann. Zeroes, Multiplicities and Idempotents for Zerodimensional Systems , Algorihtms in algebraic geometry and applications, Progress in Mathematics, vol 143. Birkhauser (1996) 1-16
M.-F. Roy, T. Van Effelterre. Aspects graphs of bodies of revolution with algorithms of real algebraic geometry. Algorihtms in algebraic geometry and applications, Progress in Mathematics, vol 143. Birkhauser (1996) 353-364
E. Becker, J.-P. Cardinal, M.-F. Roy, Z. Szafraniec. Multivariate Bezoutians, Kronecker Symbol and Eisenbud-Levine formula. Algorihtms in algebraic geometry and applications, Progress in Mathematics, vol 143. Birkhauser (1996) 79-104
A. Guergueb, J. Mainguené, M.-F. Roy. Examples of automatic theorem proving in real geometry. ISSACC 94.
M.-F. Roy, T. Van Effelterre. Aspect graphs of algebraic surfaces. ISSACC 93.
P. Pedersen, M.-F. Roy, A. Szpirglas. Counting real zeroes in the multivariate case. Dans Computational algebraic geometry, Eyssette et Galligo ed. Progress in Mathematics 109 , 203-224, Birkhaüser (1993).
J. Heintz, M.-F. Roy, P. Solerno. Single exponential path finding in semi-algebraic sets I: The case of regular bounded hypersurface. Discrete and Applied Math., Proc.AAECC-8 Tokyo, 1990; Lectures Notes in Comp. Sci. 508, Springer-Verlag (1991) 180-186.
M.-F. Roy, A. Szpirglas. Sign determinations on zero-dimensional sets. Actes de MEGA 90,Progress in Mathematics 34 457-468, Birkhaüser (1991)
H. Lombardi, M.-F. Roy. Elementary constructive theory of ordered fields. Actes de MEGA 90, Progress in Mathematics 34 249-262 Birkhaüser (1991).
J. Heintz, P. Solerno. On the complexity of semi-algebraic sets.293-298 IFIP'89 San Francisco, North-Holand (1989)
L. Gonzalez, H. Lombardi, T. Recio, M.-F. Roy. Sturm-Habicht sequence. 136-145, ISSAC'89 Portland, ACM Press.
F. Cucker, L. M. Pardo Vassallo , M. Raimondo , T. Recio, M.-F. Roy Computation of the real analytic components of a real algebraic curve . (Actes de la Conférence A.A.E.C.C.-5, Minorca). Springer Lecture Notes in Computer Science 356 161-182 (1989).
Articles dans des volumes
B. Mourrain, F. Rouillier, M.-F. Roy. Bernstein's basis and real root isolation. Current trends in combinatorial and computational geometry. Camùbridge University Press. Special volume devoted to special program "Discrete and computationalgeometry" at MSTI in its series "Mathematical Sciences Researc Institute Publications".
T. Coquand, H. Lombardi, M.-F. Roy. An elementary characterization of Krull dimension. Selected articles from a workshop in San Servolo. Venice, Italy, May 12-16, 2003. Oxford Logic Guides, Oxfort University Press.
J. Heintz, M.-F. Roy P. Solerno. Single exponential path finding in semi-algebraic sets II: The general case. Algebraic geometry and its applications. Bajaj editor, Springer Verlag (1993) 467-481.
M.-F. Roy, A. Szpirglas. Complexity of the computation of cylindrical algebraic decomposition and topology of curves, using Thom's lemma. Actes de la rencontre de géométrie algébrique réelle de Trento, 1988, Springer Lecture Notes in Mathematics 1420 223-236 (1990) .
D. Duval, M.-F. Roy. Curves and computer algebra. Springer Lecture Notes in Computer Science 391 28-42 (1989).
M.-F.Roy. Fonctions de Nash et faisceau structural sur le spectre réel. Dans: Géométrie algébrique réelle et formes quadratiques, 406-432. Lecture Notes in Math. vol. 959. Berlin Heidelberg. NewYork: Springer 1982 .
Autres rencontres scientifiques
M.-F. Roy, The role of Hilbert problems in real algebraic geometry. European Women in Mathematics, Proceedings of the 9th general meeting 189-200, Hindawi (2000).
S. Basu R. Pollack M.-F. Roy. Computing a Set of Points meeting every Cell Defined by a Family of Polynomials on a Variety, WAFR, 94, Algorithmic foundations of robotics A K Peters 537-555.
Compte-rendus à l'Académie des Sciences
R. Pollack., M.-F. Roy. On the number of cells defined by a set of polynomials. C. R. Acad. Sci. Paris 316 573-577 (1993).
J. Heintz, M.-F. Roy, P. Solerno. Description des composantes connexes d'un ensemble semi-algébrique en temps simplement exponentiel. C. R. Acad. Sci. Paris 311 167-70 (1991).
Z. Ligatsikas, M.-F. Roy. Séries de Puiseux sur un corps réel clos. C. R. Acad. Sci. Paris 311 625-628 (1990).
D. Grigor'ev, J. Heintz, M.-F. Roy, P. Solerno, N. Vorobjov. Comptage des composantes connexes d'un ensemble semi-algébrique en temps simplement exponentiel. C. R. Acad. Sci. Paris 311 879-882 (1990).
J. Heintz, M.-F. Roy P. Solerno. Complexité du principe de Tarski-Seidenberg C.R.Acad. Sci. Paris 309 825-30 (1989).
J.-P. Dedieu, M.-F. Roy. Factorisation équimodulaire des polynômes à coefficients réels et calcul formel. C. R. Acad. Sc.309 519-522 (1989).
F. Cucker, M.F. Roy. Théorèmes des zéros et positivstellensatze pour les fonctions de Nash dans le cas non-lisse . C.R. Acad. Sci. Paris 303, 563-566 (1986)
M. Coste, M.-F. Roy. Le spectre réel d'un schéma affine est spatial. C. R. Ac. Sci. Paris 290, 91-94 (1980)
M.-F. Roy. Construction d'un modèle booléen de la théorie des ensembles à partir d'un opos booléen. C. R. Ac. Sci. Paris 278, 1073-1076 (1974)
Revues diverses
J. Mainguené, .M-F. Roy. Démonstration automatique en géométrie, une approche par la géométrie analytique, Bulletin de l'APMEP n° 421 Mars -avril 1999.
M.-F. Roy. Géométrie algébrique réelle et robotique: la complexité du déménagement des pianos. Gazette des Mathematiciens, janvier 1992.
ROY, MARIE-FRANCOISE 