Prof. Felipe CUCKER

PhD – 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)

Prof. Felipe CUCKER

Contact Information

Office: Y6515 Academic 1
Phone: +852 3442-4208
Fax: +852 3442-0250
Email: macucker@cityu.edu.hk

Research Interests

  • Complexity 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. He is presently the Chairman of the Society. 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.

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. Very 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.
  • Managing Editor of the book series Library of Computational Mathematics published by Cambridge University Press.
  • Member of the board of directors of FoCM (Society for the Foundations of Computational Mathematics) since its creation in 1995.

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.

Publications – Main Refereed Articles:

  1. A Randomized Homotopy for the Hermitian Eigenpair Problem (with D. Armentano). To appear in Found. Comput. Math..
  2. Solving Second-Order Conic Systems with Finite Precision (with J. Peña and V. Roshchina). To appear in Math. Programm. .
  3. Smoothed analysis of componentwise condition numbers for sparse matrices (with D. Cheung). To appear in IMA J. of Numerical Analysis.
  4. 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.
  5. A Conditional, Collision-Avoiding, Model for Swarming (with J.-G. Dong). Discrete and Continuous Dynamical Systems A. 34, pp. 1009--1020, 2014.
  6. On the Average Condition of Random Linear Programs (with D. Cheung). SIAM J. Optimization. 23, pp. 799--810, 2013.
  7. Round-off Estimates for Second-Order Conic Feasibility Problems (with J. Peña and V. Roshchina). C. R. Acad. Sc. Paris, Ser. I 350, pp. 639--641, 2012.
  8. 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.
  9. On a Problem Posed by Steve Smale (with P. Bürgisser). Annals of Mathematics, 174, pp. 1785--1836, 2011.
  10. A General Collision-Avoiding Flocking Framework (with J.-G. Dong). IEEE Trans. Autom. Control, 56, pp. 1124--1129, 2011.
  11. Smoothed Analysis of Moore-Penrose Inversion (with P. Bürgisser). SIAM J. Matrix Anal. Appl., 31, pp. 2769--2783, 2010.
  12. Adversarial Smoothed Analysis (with R. Hauser and M. Lotz). J. of Complexity, 26, pp. 255--262, 2010.
  13. Avoiding Collisions on Flocks (with J.-G. Dong). IEEE Trans. Autom. Control, 55, pp. 1238--1243, 2010.
  14. 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.
  15. 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.
  16. 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.
  17. Componentwise Condition Numbers of Random Sparse Matrices (with D. Cheung). SIAM J. Matrix Anal. Appl. 31, pp. 721--731, 2009.
  18. Parallel Time and Quantifier Prefixes, (with P. de Naurois). Computational Complexity, 18, pp. 527--550, 2009.
  19. On the Critical Exponent for Flocks under Hierarchical Leadership, (with J.-G. Dong). Math. Mod. Methods in Appl. Sc. 19, pp. 1391--1404, 2009.
  20. Exotic Quantifiers, Complexity Classes, and Complete Problems, (with P. Buergisser). J. Found. Comput. Math. 9, pp. 135--170, 2009.
  21. 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.
  22. Flocking with Informed Agents, (with C. Huepe). Mathematics in Action, 1, pp. 1--25, 2008.
  23. 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.
  24. 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.
  25. A Condition Number for Multifold Conic Systems, (with D. Cheung and J. Peña). SIAM J. on Optim., 19, pp. 261--280, 2008.
  26. Flocking in noisy environments (with Ernesto Mordecki). J. Math. Pures et Appl., 89, pp. 278--296, 2008.
  27. A Note on Parallel and Alternating Time, (with I. Briquel). J. of Complexity, 23, pp. 594--602, 2007.
  28. Mixed and Componentwise Condition Numbers for Rectangular Structured Matrices, (with H. Diao). Calcolo, 44, pp. 89--115, 2007.
  29. The Mathematics of Emergence, (with S. Smale). Japan J. Math., 2, pp. 197--227, 2007.
  30. Emergent Behavior in Flocks, (with S. Smale). IEEE Trans. Autom. Control, 52, pp. 852--862, 2007.
  31. 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.
  32. The Complexity of Semilinear Problems in Succint Representation, (with P. Bürgisser and P. de Naurois). Computational Complexity, 15, pp. 197--235, 2006.
  33. Smoothed Analysis of Complex Conic Condition Numbers, (with P. Bürgisser and M. Lotz). J. Math. Pures et Appl., 86, pp. 293--309, 2006.
  34. General Formulas for the Smoothed Analysis of Condition Numbers, (with P. Bürgisser and M. Lotz). C. R. Acad. Sc. Paris, Ser. I 343, pp. 145--150, 2006.
  35. Solving Linear Programs with Finite Precision: II. Algorithms, (with D. Cheung). Journal of Complexity, 22, pp. 305--335, 2006.
  36. 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).
  37. 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.
  38. Smoothed Analysis for some Condition Numbers, (with Huaian Diao and Yimin Wei). Numer. Lin. Alg. with Appl., 13, pp. 17--84, 2006.
  39. 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.
  40. 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.
  41. A note on level-2 condition numbers. (with D. Cheung). J. of Complexity, 21, pp. 314--319, 2005.
  42. 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.
  43. Modelling Language Evolution,(with S. Smale and D.-X. Zhou). J. Found. of Comput. Mathematics, 4, pp. 315--343, 2004.
  44. The Complexity to Compute the Euler Characteristic of Complex Varieties, (with P. Bürgisser and M. Lotz). C. R. Acad. Sc. Paris, Ser. I 339, pp. 371--376, 2004.
  45. On sparseness, reducibilities, and complexity over the reals. Annals of Pure and Applied Logic, 134, pp. 53--61, 2005.
  46. Counting Complexity Classes for Numeric Computations I: Semilinear Sets, (with P. Bürgisser). SIAM J. on Computing, 33, pp. 227–260, 2004.
  47. Solving Linear Programs with Finite Precision: I. Condition Numbers and Random Programs, (with D. Cheung). Math. Program., 99, pp. 175–196, 2004.
  48. Unifying Condition Numbers for Linear Programming, (with D. Cheung and J.Peña). Math. of Oper. Res., 28, pp. 609–624, 2003.
  49. 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
  50. On the expected condition number of linear programming problems, (with M. Wschebor). Numerische Mathematik, 94, pp. 419–478, 2003.
  51. Learning from rounded-off data, (with D. Cheung). Information and Computation. 182, pp. 1–13, 2003.
  52. Best choices for regularization parameters in learning theory, (with S. Smale). Found. Comput. Math. 2, pp. 413–428, 2002.
  53. 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
  54. Probabilistic analysis of condition numbers for linear programming, (with D. Cheung). Journal of Optimization Theory and Applications 114, pp. 55–67, 2002.
  55. Real Computations with Fake Numbers. Journal of Complexity 18, pp. 104–134, 2002.
  56. 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.
  57. On the mathematical foundations of learning, (with S. Smale). Bulletin Amer. Math. Soc. 39, pp. 1–49, 2002.
  58. Decision problems and round-off machines, (with J.-P. Dedieu). Theory of Comp. Syst. 34, pp. 433–452, 2001.
  59. A new condition number for linear programming, (with D. Cheung). Math. Program., Ser. A, 91, pp. 163–174, 2001.
  60. There are no sparse NPW-hard sets, (with D. Grigoriev). SIAM J. on Computing 31, pp. 193–198, 2001.
  61. On Weak and Weighted Computations over the Real Closure of Q. Theoretical Computer Science 225, pp. 593–600, 2001.
  62. Complexity lower bounds for approximation algebraic computation trees, (with D.Grigoriev). Journal of Complexity 15, pp. 499–512, 1999.
  63. Approximate Zeros and Condition Numbers. Journal of Complexity 15, pp. 214–226, 1999.
  64. Complexity Estimates depending on Condition and Round-off Error, (with S. Smale). Journal of the A.C.M. 46, pp. 113–184, 1999.
  65. 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.
  66. Logics which capture complexity classes over the reals, (with K. Meer). J. of Symb. Logic, 64, pp. 363–390, 1999.
  67. Complexity and dimension, (with P. Koiran and M.Matamala). Information Processing Letters, 62, pp. 209–212, 1997.
  68. Machines over the reals and non-uniformity. Math. Logic Quarterly, 43, pp. 143–157, 1997.
  69. On the power of real Turing machines over binary inputs, (with D. Grigoriev ). SIAM J. on Comput., 26, pp.243–254, 1997.
  70. 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.
  71. 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.
  72. On Digital Nondeterminism, (with M. Matamala). Math. Syst. Theory, 29, pp. 635–647, 1996.
  73. Generalized Knapsack problems and fixed degree separations, (with M. Shub). Theoretical Comp. Science, 161, pp. 301–306, 1996.
  74. Computing over the reals with addition and order: higher complexity classes, (with P.Koiran), Journal of Complexity, 11, pp. 358–376, 1995.
  75. Separation of Complexity classes in Koiran's weak model, (with M. Shub and S.Smale), Theoretical Comp. Science, 133, pp. 3–14, 1994.
  76. On the Complexity of Quantifier Elimination: the structural approach. Computer Journal, 36(5), pp. 400–408, 1993.
  77. 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.
  78. PR ≠ NCR. Journal of Complexity, vol. 8, no 3, pp. 230–238, 1992.
  79. The arithmetical hierarchy over the reals. Journal of Logic and Computation, vol. 2, no 3, pp. 375–395, 1992.
  80. 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.
  81. Two P-complete problems in the theory of the reals, (with A. Torrecillas). Journal of Complexity. vol. 8, no 4, pp. 454–466, 1992.
  82. A theorem on random polynomials and some consequences in average complexity. (with M.-F. Roy). Journal of Symb. Comp., 10, pp. 405–409, 1990.
  83. Nondeterministic ω-computations and the analytical hierarchy. (with J. Castro). Zeit. für Math. Logik und Grund. der Math. Bd. 35, pp. 333–342, 1989.
  84. Non recursive functions have transcendental generating series, (with J. Gabarró). Inf. Théor. et Applic. R.A.I.R.O. vol. 23, no 4, pp. 445–448, 1989.
  85. Nash functions over real spectra. Journal of Pure and App. Algebra, vol. 59, pp. 43–53, 1989.
  86. Nash functions and the structure sheaf. Rocky Mountain J. of Math., vol. 19, no 3, pp. 647–649, 1989.
  87. Sur les anneaux de sections globales du faisceau structural sur le spectre réel. Comm. in Alg. vol. 16, no 2, pp. 307–323, 1988.
  88. Fonctions de Nash sur les variétés affines. Math. Zeit., Bd. 198, Heft 1, pp. 53–62, 1988.
  89. Sur la structure réelle des idéaux de C [ X1 , … , Xn ]. C. R. Math. Rep. Acad. Sci. Canada, vol. XI, no 2, pp. 113–118, 1987.
  90. Un teorema degli zeri per le funzioni de Nash. Bolletino Unione Mat. Italiana, Serie VI, vol. V-D, no 1, pp. 9–16, 1986.
  91. 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, no 12, pp. 563–566, 1986.