Publications: main refereed articles

1. On sparseness, reducibilities, and complexity over the reals. To appear in Annals of Pure and Applied Logic.
   　
2. Counting Complexity Classes for Numeric Computations I: Semilinear Sets, (with P. Bürgisser). SIAM J. on Computing, 33, pp. 227-260, 2004.
   　
3. Solving Linear Programs with Finite Precision: I. Condition Numbers and Random Programs,(with D. Cheung). Math. Program., 99, pp. 175-196, 2004.
   　
4. Unifying Condition Numbers for Linear Programming, (with D. Cheung and J.Peña). Math. of Oper. Res., 28, pp. 609-624, 2003.
   　
5. Safe recursion over an Arbitrary Structure: PAR, PH and DPH, (with Olivier Bournez,  Paulin Jacobé de Naurois, and Jean-Yves Marion).  Electronic Notes in Theor. Comp. Sc.  90, pp. 3-14, 2003. URL: http://www.elsevier.nl/locate/entcs/volume90.html
   　
6. On the expected condition number of linear programming problems, (with M. Wschebor). Numerische Mathematik, 94, pp. 419-478, 2003.
   　
7. Learning from rounded-off data, (with D. Cheung). Information and Computation. 182, pp. 1-13, 2003.
   　
8. Best choices for regularization parameters in learning theory, (with S. Smale). Found. Comput. Math. 2, pp. 413-428, 2002.
   　
9. On sparseness and Turing reducibility over the reals. Electronic Notes in Theor. Comp. Sc. 67, 2002. URL: http://www.elsevier.nl/locate/entcs/volume67.html
   　
10. Probabilistic analysis of condition numbers for linear programming, (with D. Cheung). Journal of Optimization Theory and Applications 114, pp. 55-67, 2002.
    　
11. Real Computations with Fake Numbers.  Journal of Complexity 18, pp. 104-134, 2002.
    　
12. A primal-dual algorithm for solving polyhedral conic systems with a finite-precision machine, (with J. Peña). SIAM J. on Optimization 12, pp. 522-554, 2002.
    　
13. On the mathematical foundations of learning, (with S. Smale). Bulletin Amer. Math. Soc. 39, pp. 1-49, 2002.
    　
14. Decision problems and round-off machines, (with J.-P. Dedieu). Theory of Comp. Syst. 34, pp. 433-452, 2001.
    　
15. A new condition number for linear programming, (with D. Cheung). Math. Program., Ser. A, 91, pp. 163-174, 2001.
    　
16. There are no NP_W-hard sets, (with D. Grigoriev). SIAM J. on Computing 31, pp. 193-198, 2001.
    　
17. On Weak and Weighted Computations over the Real Closure of Q. Theoretical Computer Science 225, pp. 593-600, 2001.
    　
18. Complexity lower bounds for approximation algebraic computation trees, (with D. Grigoriev). Journal of Complexity 15, pp. 499-512, 1999.
    　
19. Approximate Zeros and Condition Numbers.  Journal of Complexity 15, pp. 214-226, 1999.
    　
20. Complexity Estimates depending on Condition and Round-off Error, (with S. Smale). Journal of the A.C.M. 46, pp. 113-184, 1999.
    　
21. A Polynomial Time Algorithm for Diophantine Equations in One Variable, (with P. Koiran and S. Smale). Journal of Symb. Comp. 27, pp. 21-29, 1999.
    　
22. Logics which capture complexity classes over the reals, (with K. Meer). J. of Symb. Logic, 64, pp. 363-390, 1999.
    　
23. Complexity and dimension, (with P. Koiran and M. Matamala). Information Processing Letters, 62, pp. 209-212, 1997.
    　
24. Machines over the reals and non-uniformity. Math. Logic Quarterly, 43, pp. 143-157, 1997.
    　
25. On the power of real Turing machines over binary inputs, (with D. Grigoriev ). SIAM J. on Comput., 26, pp.243-254, 1997.
    　
26. Complexity and Real Computation: a Manifesto, (with L. Blum, M. Shub and S. Smale). Int. J. of Bifurcation and Chaos, 6(1), pp. 3-26, 1996.
    　
27. On real Turing machines that toss coins, (with M. Karpinski, P. Koiran, T. Lickteig and K. Werther). Proceedings of ACM Symp. on Theory of Computing, pp. 335-342, 1995.
    　
28. On Digital Nondeterminism, (with M. Matamala). Math. Syst. Theory, 29, pp. 635-647, 1996.
    　
29. Generalized Knapsack problems and fixed degree separations, (with M. Shub). Theoretical Comp. Science, 161, pp. 301-306, 1996.
    　
30. Computing over the reals with addition and order: higher complexity classes, (with P. Koiran), Journal of Complexity, 11, pp. 358-376, 1995.
    　
31. Separation of Complexity classes in Koiran's weak model, (with M. Shub and S. Smale), Theoretical Comp. Science, 133, pp. 3-14, 1994.
    　
32. On the Complexity of Quantifier Elimination: the structural approach. Computer Journal, 36(5), pp. 400-408, 1993.
    　
33. Time bounded computations over the reals, (with J.L. Montaña and L.M. Pardo). Int. J. of Algebra and Computation, 2, pp. 395-408, 1992.
    　
34. P_R ≠ NC_R. Journal of Complexity, vol. 8, n^o 3, pp. 230-238, 1992.
    　
35. The arithmetical hierarchy over the reals. Journal of Logic and Computation, vol. 2, n^o 3, pp. 375-395, 1992.
    　
36. Real algebraic numbers are in NC, (with H. Lanneau, B. Mishra, P. Pedersen and M.-F. Roy). App. Alg. in Eng. Comm. and Comp. 3, pp.79-98, 1992.
    　
37. Two P-complete problems in the theory of the reals, (with A. Torrecillas). Journal of Complexity. vol. 8, n^o 4, pp. 454-466, 1992.
    　
38. A theorem on random polynomials and some consequences in average complexity. (with M.-F. Roy). Journal of Symb. Comp., 10, pp. 405-409, 1990.
    　
39. Nondeterministic ω-computations and the analytical hierarchy. (with J. Castro). Zeit. für Math. Logik und Grund. der Math. Bd. 35, pp. 333-342, 1989.
    　
40. Non recursive functions have transcendental generating series, (with J. Gabarró). Inf. Théor. et Applic. R.A.I.R.O. vol. 23, n^o 4, pp. 445-448, 1989.
    　
41. Nash functions over real spectra. Journal of Pure and App. Algebra, vol. 59, pp. 43-53, 1989.
    　
42. Nash functions and the structure sheaf. Rocky Mountain J. of Math., vol. 19 , n^o 3, pp. 647-649, 1989.
    　
43. Sur les anneaux de sections globales du faisceau structural sur le spectre réel. Comm. in Alg. vol. 16, n^o 2, pp. 307-323, 1988.
    　
44. Fonctions de Nash sur les variétés affines. Math. Zeit., Bd. 198, Heft 1, pp. 53-62, 1988.
    　
45. Sur la structure réelle des idéaux de C[X₁,...,X_n]. C. R. Math. Rep. Acad. Sci. Canada, vol. XI, n^o 2, pp. 113-118, 1987.
    　
46. Un teorema degli zeri per le funzioni de Nash. Bolletino Unione Mat. Italiana, Serie VI, vol. V-D, n^o 1, pp. 9-16, 1986.
    　
47. Théorèmes des zéros et Positivstellensatz pour les fonctions de Nash dans le cas non lisse, (with M.-F. Roy), C. R. Acad. Sc. Paris, t. 303, Série I, n^o 12, pp. 563-566, 1986.