Erich Kaltofen

Erich Kaltofen

Erich Kaltofen

Erich Kaltofen est professeur à North Carolina State University. Il a été professeur invité au Mathematical Sciences Research Institute à Berkeley (MSRI), à l’université de Toronto, à l’ENS de Lyon et au MIT. Ses domaines de recherche sont le calcul symbolique et l’informatique théorique. Ses recherches actuelles concernent le calcul hybride symbolique-numérique, la complexité des certificats de somme de carrés pour les optimaux globaux, l’algorithmique exact en algèbre linéaire dans le cadre du projet LinBox.

Erich Kaltofen a reçu le prix IBM Faculty Development, a été Chair de SIGSAM (ACM Special Interest Group on Symbolic and Algebraic Manipulation) et a été promu ACM fellow en 2009. Il a co-édité Computer Algebra Handbook en 2002.

Complexity Theory and Symbolic Computation

The discipline of symbolic computation goes back to be beginnings of computers, as early on scientists carried out symbolic (exact) and algebraic manipulation of polynomials and quantified formulas on early computers.  The theory of  NP-completeness exposed many of the investigated problems hard in the worst case.  As it turned out in the 1980s, an exception is the problem of polynomial factoring, that unlike the problem of integer factoring is in random polynomial time even when representing the input polynomial by a straight-line program.

Today’s highly sophisticated and finely tuned algorithms, e.g., for Groebner basis reduction and real algebraic geometry, can solve many of the mathematical problems arising in science and engineering.  As has Alan Turing in his practical work, symbolic and hybrid symbolic-numeric methods operate on the fine line between the doable and the hard, that also when the difference is a quadratic vs. a linear complexity but when the intermediate data is exceedingly large.

By way of examples ranging from sparse linear algebra over factorization to non-linear optimization, in my talk I will attempt to separate problem instances that are doable from those that are provably hard.

This entry was posted in Conférenciers invités. Bookmark the permalink.

Comments are closed.