Leitung

Prof. Dr. Peter Bürgisser

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

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

eMail
pbuerg@math.tu-berlin.de
contact form

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.

Test complexity of generic polynomials
Zitatschlüssel	BLS-Test-Complexity-Of-Generic-Polynomials
Autor	Peter Bürgisser and Thomas Lickteig and Michael Shub
Seiten	203-215
Jahr	1992
DOI	10.1016/0885-064X(92)90022-4
Journal	J. Compl.
Jahrgang	8
Nummer	3
Zusammenfassung	We investigate the complexity of algebraic decision trees deciding membership in a hypersurface $X$ in $\mathbb C^m$. We prove an optimal lower bound on the number of additions, subtractions and comparisons and an asymptotically optimal lower bound on the number of multiplications, divisions and comparisons that are needed to decide membership in a generic hypersurface $X$ in $\mathbb C^m$. Over the reals, where in addition to equality branching also $<$-branching is allowed, we prove an analoguous statement for irreducible ``generic'' hypersurfaces $X$ in $\mathbb R^m$. In the case $m=1$ we give also a lower bound for finite subsets $X$ in $\mathbb R$.

Schnellnavigation zur Seite über Nummerneingabe

Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.