direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

There is no English translation for this web page.

In Proceedings

Algebraische Komplexitaetstheorie I - Eine Einfuehrung
Citation key BC-Algebraische-Komplexitaetstheorie-I-Eine-Einfuehrung
Author Peter Bürgisser and Michael Hermann Clausen
Title of Book Seminaire Lotharingien de Combinatoire
Pages 1-18
Year 1996
Number B36a
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.
Link to publication Link to original publication Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.