Personal tools
You are here: Home / Events / Symbolic Computation and Complexity Theory

Symbolic Computation and Complexity Theory

Filed under:
Professor Erich Kaltofen, North Carolina State University, 11 November 2013, 1.30 p.m., RISC Seminarroom pond
When Nov 11, 2013
from 01:30 PM to 03:00 PM
Where RISC Seminarroom pond
Add event to calendar vCal
iCal

Symbolic Computation and Complexity Theory

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 has 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. 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 sparse multidimensional model synthesis, in my talk I will attempt to separate algorithmic problems that are doable from those that areprovably hard.  I will give my answer on the role of algorithms whoserunning time is exponential in input size.