TU Berlin

Fachgebiet Algorithmische AlgebraProf. Dr. Peter Bürgisser

Inhalt des Dokuments

zur Navigation

Leitung

Prof. Dr. Peter Bürgisser

Lupe

Anschrift
Technische Universität Berlin
Institut für Mathematik
Sekretariat MA 3-2
Straße des 17. Juni 136
10623 Berlin

Büro
Raum MA 317 (3. OG)
Institut für Mathematik

Kontakt

Sekretariat
Beate Nießen
Raum MA 318
Tel.: +49 (0)30 314 - 25771

eMail
peter.buergisser@offmath.tu-berlin.de

Telefon
+49 (0)30 314 - 75902
Faxgerät
+49 (0)30 314 - 25839

Sprechstunde
Während der Vorlesungszeit: Do, 15-16 Uhr.
Während der vorlesungsfreien Zeit: nach Vereinbarung.

Publikationen

Algebraische Komplexitaetstheorie I - Eine Einfuehrung
Zitatschlüssel BC-Algebraische-Komplexitaetstheorie-I-Eine-Einfuehrung
Autor Peter Bürgisser and Michael Hermann Clausen
Buchtitel Seminaire Lotharingien de Combinatoire
Seiten 1-18
Jahr 1996
Nummer B36a
Zusammenfassung 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 zur Publikation Link zur Originalpublikation Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe