Séminaire Lotharingien de Combinatoire, B36a (1996), 18pp.
Peter Bürgisser and Michael Clausen
Algebraische Komplexitätstheorie I:
Eine Einführung
Abstract.
Algebraic complexity theory is the study of the intrinsic algorithmic difficulty
of algebraic problems within an algebraic model of computation. Motivated by
questions of numerical and symbolic computation, this branch of research originated
in 1954 when Ostrowski inquired about the optimality of Horner's rule. We survey
some of the techniques for proving lower bounds in the straight-line and
computation tree model. Among these are Strassen's degree bound, which relies on the
concept of the degree of an affine variety, as well as lower bounds in terms of
the number of connected components (or higher Betti numbers) of semi-algebraic sets.
As a particular application of these methods we discuss the optimality of the
Knuth-Schönhage algorithm for computing the GCD of two univariate polynomials.
The following versions are available: