Erich Kaltofen
Erich Kaltofen is a Professor at North Carolina State University. He has held visiting positions at MSRI in Berkeley, the University of Toronto, the ENS Lyon, and MIT. His research is in symbolic computation and theoretical computer science. His current interests are in hybrid symbolic-numeric computation, the complexity of sum-of-squares certificates for global optima, and exact linear algebra algorithms under the auspices of the LinBox project. His former Ph.D. students work at Facebook, Google, IBM, Maplesoft, the University of Antwerp and other academic institutions.
Kaltofen held an IBM Faculty Development Award, was the Chair of ACM’s SIGSAM, and in 2009 was inducted as an ACM Fellow. He has co-edited the 2002 Computer Algebra Handbook. According to Microsoft Academic Search, he is a highly cited author in Scientific Computation.
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.
