Prof. Felipe CUCKERPhD – Université de Rennes, France
PhD – Universidad de Cantabria, Spain (Premio extraordinario de doctorade)
Chair Professor, City University of Hong Kong

Catedrático de Lenguajes y Sistemas Informáticos, Universidad Pompeu Fabra (en excedencia)
Contact InformationOffice:P6713 Academic 1
Phone:+852 3442-4208
Fax:+852 3442-0250
Email:macucker@cityu.edu.hk
Research InterestsComplexity and Computation

Prof Felipe Cucker’s main research focus is on the foundational aspects of numerical algorithms. This encompasses a variety of issues from the structural complexity of algorithms over the real numbers to the roundoff analysis of specific algorithms, from the smoothed analysis of classes of condition numbers to the design of numerical algorithms for specific problems. In addition, he is also interested on other areas of research such as learning theory or the mathematics of emergent behaviour.
Prof Cucker has been a member of the Board of Directors of the Society for the Foundations of Computational Mathematics since its creation until 2017 and was the Chairman of the Society in the period 2008-2011. He either is or was a member of the editorial board of the journals Foundations of Computational Mathematics, Journal of complexity, SIAM Journal on Optimization, and Theoretical Computer Science. In 2005 he was made Foreign Member of the Real Academia de Ciencias y Artes de Barcelona, and in 2018 Foreign Member of the European Academy of Sciences.
Research InterestIt evolved from real algebra and geometry (in both theoretical and computational aspects) to complexity theory. Between 1983 and 1986 it dealt with the properties of rings of Nash functions over algebraic varieties. From 1987 to 1990 the focus of the research was on the algorithmic side of real algebraic geometry, i.e., the design and analysis of algorithms for problems in this field. From 1990, it deals with the structural approach to the complexity of these problems following the Blum, Shub & Smale model. In the last few years it evolved to include the numerical analysis of some algorithms in optimization. More recently, it has also included areas such as learning theory and problems like the mathematical modelling of human language evolution.
Professional ResponsibilitiesMember of the Editorial Board of the Journal of Complexity.
Managing Editor of the Journal of Foundations on Computational Mathematics, 2011-2017.
Member of the board of directors of FoCM (Society for the Foundations of Computational Mathematics) since its creation in 1995 until 2017. Chairman of FoCM, 2008-2011.
BooksCondition (with P. Bürgisser). Volume 349 in the series "Grundlehren der mathematischen Wissenschaften
/ma/doc/people/cuckerf/turing.pdf" target="_blank">On sparseness, reducibilities, and complexity over the reals. Annals of Pure and Applied Logic, 134, pp. 53--61, 2005.
Counting Complexity Classes for Numeric Computations I: Semilinear Sets, (with P. Bürgisser). SIAM J. on Computing, 33, pp. 227–260, 2004.
Solving Linear Programs with Finite Precision: I. Condition Numbers and Random Programs, (with D. Cheung). Math. Program., 99, pp. 175–196, 2004.
Unifying Condition Numbers for Linear Programming, (with D. Cheung and J.Peña). Math. of Oper. Res., 28, pp. 609–624, 2003.
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
On the expected condition number of linear programming problems, (with M. Wschebor). Numerische Mathematik, 94, pp. 419–478, 2003.
Learning from rounded-off data, (with D. Cheung). Information and Computation. 182, pp. 1–13, 2003.
Best choices for regularization parameters in learning theory, (with S. Smale). Found. Comput. Math. 2, pp. 413–428, 2002.
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
Probabilistic analysis of condition numbers for linear programming, (with D. Cheung). Journal of Optimization Theory and Applications 114, pp. 55–67, 2002.
Real Computations with Fake Numbers. Journal of Complexity 18, pp. 104–134, 2002.
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.
On the mathematical foundations of learning, (with S. Smale). Bulletin Amer. Math. Soc. 39, pp. 1–49, 2002.
Decision problems and round-off machines, (with J.-P. Dedieu). Theory of Comp. Syst. 34, pp. 433–452, 2001.
A new condition number for linear programming, (with D. Cheung). Math. Program., Ser. A, 91, pp. 163–174, 2001.
There are no sparse NPW-hard sets, (with D. Grigoriev). SIAM J. on Computing 31, pp. 193–198, 2001.
On Weak and Weighted Computations over the Real Closure of Q. Theoretical Computer Science 225, pp. 593–600, 2001.
Complexity lower bounds for approximation algebraic computation trees, (with D.Grigoriev). Journal of Complexity 15, pp. 499–512, 1999.
Approximate Zeros and Condition Numbers. Journal of Complexity 15, pp. 214–226, 1999.
Complexity Estimates depending on Condition and Round-off Error, (with S. Smale). Journal of the A.C.M. 46, pp. 113–184, 1999.
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.
Logics which capture complexity classes over the reals, (with K. Meer). J. of Symb. Logic, 64, pp. 363–390, 1999.
Complexity and dimension, (with P. Koiran and M.Matamala). Information Processing Letters, 62, pp. 209–212, 1997.
Machines over the reals and non-uniformity. Math. Logic Quarterly, 43, pp. 143–157, 1997.
On the power of real Turing machines over binary inputs, (with D. Grigoriev ). SIAM J. on Comput., 26, pp.243–254, 1997.
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.
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.
On Digital Nondeterminism, (with M. Matamala). Math. Syst. Theory, 29, pp. 635–647, 1996.
Generalized Knapsack problems and fixed degree separations, (with M. Shub). Theoretical Comp. Science, 161, pp. 301–306, 1996.
Computing over the reals with addition and order: higher complexity classes, (with P.Koiran), Journal of Complexity, 11, pp. 358–376, 1995.
Separation of Complexity classes in Koiran's weak model, (with M. Shub and S.Smale), Theoretical Comp. Science, 133, pp. 3–14, 1994.
On the Complexity of Quantifier Elimination: the structural approach. Computer Journal, 36(5), pp. 400–408, 1993.
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.
P_R ≠ NC_R. Journal of Complexity, vol. 8, n^o 3, pp. 230–238, 1992.
The arithmetical hierarchy over the reals. Journal of Logic and Computation, vol. 2, n^o 3, pp. 375–395, 1992.
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.
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.
A theorem on random polynomials and some consequences in average complexity. (with M.-F. Roy). Journal of Symb. Comp., 10, pp. 405–409, 1990.
Nondeterministic ω-computations and the analytical hierarchy. (with J. Castro). Zeit. für Math. Logik und Grund. der Math. Bd. 35, pp. 333–342, 1989.
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.
Nash functions over real spectra. Journal of Pure and App. Algebra, vol. 59, pp. 43–53, 1989.
Nash functions and the structure sheaf. Rocky Mountain J. of Math., vol. 19, n^o 3, pp. 647–649, 1989.
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.
Fonctions de Nash sur les variétés affines. Math. Zeit., Bd. 198, Heft 1, pp. 53–62, 1988.
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.
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.
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.