Algebraic complexity theory / Peter Bürgisser, Michael Clausen, M. Amin Shokrollahi ; with the collaboration of Thomas Lickteig

Within the general theory of computational complexity, algebraic complexity theory can be distinguished by the source of its problems (algebra) and by its stress on symbolic (as opposed to numerical) aspects in computational models. Among others, the book discusses the following fundamental problems: multiplication of polynomials; multiplication, inversion and composition of power series; computing the greatest common divisor of polynomials; polynomial interpolation and evaluation of polynomials; matrix multiplication; inversion and other problems of (bi)linear algebra. The main computational models are the straight-line program and the computation tree.
The authors stress that there is a difference between algebraic complexity and computer algebra. The book emphasizes proving lower bounds on complexity, that is, proving that a given problem cannot be solved faster than in a particular time. On the other hand, computer algebra deals with upper bounds on complexity for algorithmic problems in algebra. Naturally, proving a good upper bound reduces to constructing an efficient algorithm. Proving a nontrivial lower bound may turn out to be quite difficult and often requires an advanced technique even if the problem is "elementary'' and the bound looks "obvious''. ... (MathSciNet)