Prof. Felipe CUCKER
Chair Professor
PhD – Université de Rennes, France
PhD – Universidad de Cantabria, Spain (Premio extraordinario de doctorade)
YEUNG-Y6519
3442-0250
3442-4208
macucker@cityu.edu.hk
img alt

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 Interest

It 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 Responsibilities
  • Member 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.
Books
  1. Condition(with P. Bürgisser). Volume 349 in the series "Grundlehren der mathematischen Wissenschaften", Springer-Verlag, 2013.
  2. Manifold Mirrors: The Crossing Paths of the Arts and Mathematics, Cambridge Univ. Press, 2013.
  3. Learning Theory: An Approximation Theory Viewpoint(with D.-X. Zhou). Cambridge Monographs on Applied and Computational Mathematics, Cambridge Univ. Press, 2007.
  4. Complexity and Real Computation(with L. Blum, M. Shub and S. Smale). Springer-Verlag, New York, 1998.
  5. Curso de Programación(with J. Castro, X. Messeguer, A. Rubio, Ll. Solano and B. Valles). McGraw-Hill, Madrid, 1993.
Research Interests
  • Complexity and Computation
Publications – Main Refereed Articles:
  1. Computing the Homology of Semialgebraic Sets. II: General Formulas (with P Bürgisser and J. Tonelli Cueto). To appear inFound. Comput. Math..
  2. On local complexity (with T. Krick).J. of Complexity,57, 101442, 23 pages, 2020.
  3. Computing the Homology of Semialgebraic Sets. I: Lax Formulas (with P Bürgisser and J. Tonelli Cueto).Found. Comput. Math.,20, pp. 71-118, 2020.
  4. On flocks under switching directed interaction topologies (with J.-G. Dong).SIAM J. App. Math.,79, pp. 95-110, 2019.
  5. Computing the Homology of Basic Semialgebraic Sets in Weak Exponential Time (with P. Bürgisser and P. Lairez).J. of the ACM,66, pp. 5:1-5:30, 2019.
  6. Computing the Homology of Real Projective Sets (with T. Krick and M. Shub).Found. Comput. Math.,18, pp. 929-970, 2018.
  7. A stable, polynomial-time algorithm for the eigenpair problem (with D. Armentano, C. Beltrán, P.Bürgisser, and M. Shub).J. Eur. Math. Soc.,20, pp. 1375-1437, 2018.
  8. Grid Methods in Computational Real Algebraic (and Semialgebraic) Geometry.Chinese Annals of Mathematics, Series B,39, pp. 373–396, 2018.
  9. On the Condition of the Zeros of Characteristic polynomials (with P. Bürgisser and E. Rocha Cardozo).J. of Complexity,42, pp. 72–84, 2017.
  10. On Flocks Influenced by Closest Neighbors (with J.-G. Dong).Math. Mod. Methods in Appl. Sc.26, pp. 2685-2708, 2016.
  11. Condition length and complexity for the solution of polynomial systems (with D. Armentano, C. Beltrán, P.Bürgisser, and M. Shub). Found. Comput. Math,16, pp.1401-1422, 2016.
  12. Probabilistic Analyses of Condition Numbers.Acta Numerica,25, pp. 321-382, 2016.
  13. A Theory of Complexity, Condition, and Roundoff.Forum of Mathematics, Sigma,3, e4, 2015.
  14. A Randomized Homotopy for the Hermitian Eigenpair Problem (with D. Armentano).Found. Comput. Math.,15, pp. 281-312, 2015.
  15. Solving Second-Order Conic Systems with Finite Precision (with J. Peña and V. Roshchina).Math. Programm.,150, pp. 217-250, 2015.
  16. Smoothed analysis of componentwise condition numbers for sparse matrices (with D. Cheung).IMA J. of Numerical Analysis,35, pp.74-88, 2015.
  17. Fast Computation of Zeros of Polynomial Systems with Bounded Degree under Finite-precision (with I. Briquel, J. Peña and V. Roshchina).Math. of Comput.83, pp. 1279--1317, 2014.
  18. A Conditional, Collision-Avoiding, Model for Swarming (with J.-G. Dong).Discrete and Continuous Dynamical Systems A.34, pp. 1009--1020, 2014.
  19. On the Average Condition of Random Linear Programs (with D. Cheung).SIAM J. Optimization.23, pp. 799--810, 2013.
  20. Round-off Estimates for Second-Order Conic Feasibility Problems (with J. Peña and V. Roshchina).C. R. Acad. Sc. Paris, Ser. I350, pp. 639--641, 2012.
  21. A Numerical Algorithm for Zero Counting. III: Randomization and Condition (with T. Krick, G. Malajovich and M. Wschebor).Adv. Applied Math.,48, pp. 215--248, 2012.
  22. On a Problem Posed by Steve Smale (with P. Bürgisser).Annals of Mathematics,174, pp. 1785--1836, 2011.
  23. A General Collision-Avoiding Flocking Framework (with J.-G. Dong).IEEE Trans. Autom. Control,56, pp. 1124--1129, 2011.
  24. Smoothed Analysis of Moore-Penrose Inversion (with P. Bürgisser).SIAM J. Matrix Anal. Appl.,31, pp. 2769--2783, 2010.
  25. Adversarial Smoothed Analysis (with R. Hauser and M. Lotz).J. of Complexity,26, pp. 255--262, 2010.
  26. Avoiding Collisions on Flocks (with J.-G. Dong).IEEE Trans. Autom. Control,55, pp. 1238--1243, 2010.
  27. On Strata of Degenerate Polyhedral Cones. II: Relations between Condition Measures, (with D. Cheung and J. Peña).J. of Complexity,26, pp. 209--226, 2010.
  28. Coverage Processes on Spheres and Condition Numbers for Linear Programming (with P. Bürgisser and M. Lotz).Annals of Probability,38, pp. 570--604, 2010.
  29. A Numerical Algorithm for Zero Counting. II: Distance to Ill-posedness and Smoothed Analysis (with T. Krick, G. Malajovich and M. Wschebor).J. Fixed Point Theory Appl.6, pp. 285--294, 2009.
  30. Componentwise Condition Numbers of Random Sparse Matrices (with D. Cheung).SIAM J. Matrix Anal. Appl.31, pp. 721--731, 2009.
  31. Parallel Time and Quantifier Prefixes, (with P. de Naurois).Computational Complexity,18, pp. 527--550, 2009.
  32. On the Critical Exponent for Flocks under Hierarchical Leadership, (with J.-G. Dong).Math. Mod. Methods in Appl. Sc.19, pp. 1391--1404, 2009.
  33. Exotic Quantifiers, Complexity Classes, and Complete Problems, (with P. Buergisser).J. Found. Comput. Math.9, pp. 135--170, 2009.
  34. On Strata of Degenerate Polyhedral Cones. I: Condition and Distance to Stratae, (with D. Cheung and J. Peña).European J. Oper. Res.,198, pp. 23--28, 2009.
  35. Flocking with Informed Agents, (with C. Huepe).Mathematics in Action,1, pp. 1--25, 2008.
  36. A Numerical Algorithm for Zero Counting. I: Complexity and Accuracy, (with T. Krick, G. Malajovich and M. Wschebor).J. of Complexity,24, pp. 582--605, 2008.
  37. The Probability that a Slightly Perturbed Numerical Analysis Problem is Difficult, (with P. Bürgisser and M. Lotz).Mathematics of Computation,77, pp. 1559--1583, 2008.
  38. A Condition Number for Multifold Conic Systems, (with D. Cheung and J. Peña).SIAM J. on Optim.,19, pp. 261--280, 2008.
  39. Flocking in noisy environments (with Ernesto Mordecki).J. Math. Pures et Appl.,89, pp. 278--296, 2008.
  40. A Note on Parallel and Alternating Time, (with I. Briquel).J. of Complexity,23, pp. 594--602, 2007.
  41. Mixed and Componentwise Condition Numbers for Rectangular Structured Matrices, (with H. Diao).Calcolo,44, pp. 89--115, 2007.
  42. The Mathematics of Emergence, (with S. Smale).Japan J. Math.,2, pp. 197--227, 2007.
  43. Emergent Behavior in Flocks, (with S. Smale).IEEE Trans. Autom. Control,52, pp. 852--862, 2007.
  44. On Mixed and Componentwise Condition Numbers for Moore-Penrose Inverse and Linear Least Squares Problems, (with H. Diao and Y. Wei).Mathematics of Computation,76, pp. 947--963, 2007.
  45. The Complexity of Semilinear Problems in Succint Representation, (with P. Bürgisser and P. de Naurois).Computational Complexity,15, pp. 197--235, 2006.
  46. Smoothed Analysis of Complex Conic Condition Numbers, (with P. Bürgisser and M. Lotz).J. Math. Pures et Appl.,86, pp. 293--309, 2006.
  47. General Formulas for the Smoothed Analysis of Condition Numbers, (with P. Bürgisser and M. Lotz).C. R. Acad. Sc. Paris, Ser. I343, pp. 145--150, 2006.
  48. Solving Linear Programs with Finite Precision: II. Algorithms, (with D. Cheung).Journal of Complexity,22, pp. 305--335, 2006.
  49. Counting Complexity Classes for Numeric Computations II: Algebraic and Semialgebraic Sets, (with P. Bürgisser).Journal of Complexity,22, pp. 147--191, 2006. (An extended abstract appeared at Proc. 36th ACM Symp. Theory of Computing, 2004, pp. 475--485).
  50. Implicit Complexity over an Arbitrary Structure: Quantifier Alternations, (with O. Bournez, P. de Naurois, and J.-Y. Marion).Information and Computation,204, pp. 210--230, 2006.
  51. Smoothed Analysis for some Condition Numbers, (with Huaian Diao and Yimin Wei).Numer. Lin. Alg. with Appl.,13, pp. 17--84, 2006.
  52. Counting Complexity Classes for Numeric Computations III: Complex Projective Sets, (with P. Bürgisser and M. Lotz).J. Found. Comput. Math.,5, pp. 351--387, 2005.
  53. On tail decay and moment estimates of a condition number for random linear conic systems, (with D. Cheung and R. Hauser).SIAM J. Optim.,15, pp. 1237--1261, 2005.
  54. A note on level-2 condition numbers. (with D. Cheung).J. of Complexity,21, pp. 314--319, 2005.
  55. Implicit Complexity over an Arbitrary Structure: Sequential and Parallel Polynomial Time, (with Olivier Bournez, Paulin Jacobé de Naurois, and Jean-Yves Marion).J. of Logic and Computation,15, pp. 41--58, 2005.
  56. Modelling Language Evolution,(with S. Smale and D.-X. Zhou).J. Found. of Comput. Mathematics,4, pp. 315--343, 2004.
  57. The Complexity to Compute the Euler Characteristic of Complex Varieties, (with P. Bürgisser and M. Lotz).C. R. Acad. Sc. Paris, Ser. I339, pp. 371--376, 2004.
  58. On sparseness, reducibilities, and complexity over the reals. Annals of Pure and Applied Logic,134, pp. 53--61, 2005.
  59. Counting Complexity Classes for Numeric Computations I: Semilinear Sets, (with P. Bürgisser).SIAM J. on Computing,33, pp. 227–260, 2004.
  60. Solving Linear Programs with Finite Precision: I. Condition Numbers and Random Programs, (with D. Cheung).Math. Program.,99, pp. 175–196, 2004.
  61. Unifying Condition Numbers for Linear Programming, (with D. Cheung and J.Peña).Math. of Oper. Res.,28, pp. 609–624, 2003.
  62. 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
  63. On the expected condition number of linear programming problems, (with M. Wschebor).Numerische Mathematik,94, pp. 419–478, 2003.
  64. Learning from rounded-off data, (with D. Cheung).Information and Computation.182, pp. 1–13, 2003.
  65. Best choices for regularization parameters in learning theory, (with S. Smale).Found. Comput. Math.2, pp. 413–428, 2002.
  66. 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
  67. Probabilistic analysis of condition numbers for linear programming, (with D. Cheung).Journal of Optimization Theory and Applications114, pp. 55–67, 2002.
  68. Real Computations with Fake Numbers.Journal of Complexity18, pp. 104–134, 2002.
  69. A primal-dual algorithm for solving polyhedral conic systems with a finite-precision machine, (with J. Peña).SIAM J. on Optimization12, pp. 522–554, 2002.
  70. On the mathematical foundations of learning, (with S. Smale).Bulletin Amer. Math. Soc.39, pp. 1–49, 2002.
  71. Decision problems and round-off machines, (with J.-P. Dedieu).Theory of Comp. Syst.34, pp. 433–452, 2001.
  72. A new condition number for linear programming, (with D. Cheung).Math. Program., Ser. A,91, pp. 163–174, 2001.
  73. There are no sparse NPW-hard sets, (with D. Grigoriev).SIAM J. on Computing31, pp. 193–198, 2001.
  74. On Weak and Weighted Computations over the Real Closure ofQ.Theoretical Computer Science225, pp. 593–600, 2001.
  75. Complexity lower bounds for approximation algebraic computation trees, (with D.Grigoriev).Journal of Complexity15, pp. 499–512, 1999.
  76. Approximate Zeros and Condition Numbers.Journal of Complexity15, pp. 214–226, 1999.
  77. Complexity Estimates depending on Condition and Round-off Error, (with S. Smale).Journal of the A.C.M.46, pp. 113–184, 1999.
  78. 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.
  79. Logics which capture complexity classes over the reals, (with K. Meer).J. of Symb. Logic,64, pp. 363–390, 1999.
  80. Complexity and dimension, (with P. Koiran and M.Matamala).Information Processing Letters,62, pp. 209–212, 1997.
  81. Machines over the reals and non-uniformity.Math. Logic Quarterly,43, pp. 143–157, 1997.
  82. On the power of real Turing machines over binary inputs, (with D. Grigoriev ).SIAM J. on Comput.,26, pp.243–254, 1997.
  83. 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.
  84. 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.
  85. On Digital Nondeterminism, (with M. Matamala).Math. Syst. Theory,29, pp. 635–647, 1996.
  86. Generalized Knapsack problems and fixed degree separations, (with M. Shub).Theoretical Comp. Science,161, pp. 301–306, 1996.
  87. Computing over the reals with addition and order: higher complexity classes, (with P.Koiran),Journal of Complexity,11, pp. 358–376, 1995.
  88. Separation of Complexity classes in Koiran's weak model, (with M. Shub and S.Smale),Theoretical Comp. Science,133, pp. 3–14, 1994.
  89. On the Complexity of Quantifier Elimination: the structural approach.Computer Journal,36(5), pp. 400–408, 1993.
  90. 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.
  91. PR≠ NCR.Journal of Complexity, vol.8, no3, pp. 230–238, 1992.
  92. The arithmetical hierarchy over the reals.Journal of Logic and Computation, vol. 2, no3, pp. 375–395, 1992.
  93. 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.
  94. Two P-complete problems in the theory of the reals, (with A. Torrecillas).Journal of Complexity. vol.8, no4, pp. 454–466, 1992.
  95. A theorem on random polynomials and some consequences in average complexity. (with M.-F. Roy).Journal of Symb. Comp.,10, pp. 405–409, 1990.
  96. Nondeterministicω-computations and the analytical hierarchy. (with J. Castro).Zeit. für Math. Logik und Grund. der Math. Bd.35, pp. 333–342, 1989.
  97. Non recursive functions have transcendental generating series, (with J. Gabarró).Inf. Théor. et Applic. R.A.I.R.O.vol.23, no4, pp. 445–448, 1989.
  98. Nash functions over real spectra.Journal of Pure and App. Algebra, vol.59, pp. 43–53, 1989.
  99. Nash functions and the structure sheaf.Rocky Mountain J. of Math., vol.19, no3, pp. 647–649, 1989.
  100. Sur les anneaux de sections globales du faisceau structural sur le spectre réel.Comm. in Alg. vol.16, no2, pp. 307–323, 1988.
  101. Fonctions de Nash sur les variétés affines.Math. Zeit., Bd.198, Heft 1, pp. 53–62, 1988.
  102. Sur la structure réelle des idéaux deC [ X1, … , Xn].C. R. Math. Rep. Acad. Sci. Canada, vol. XI, no2, pp. 113–118, 1987.
  103. Un teorema degli zeri per le funzioni de Nash.Bolletino Unione Mat. Italiana, Serie VI, vol. V-D, no1, pp. 9–16, 1986.
  104. 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, no12, pp. 563–566, 1986.

Useful Links

CityU Scholars:

https://scholars.cityu.edu.hk