TU Berlin

Fachgebiet Algorithmische AlgebraProf. Dr. Peter Bürgisser

Page Content

to Navigation


Prof. Dr. Peter Bürgisser


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

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


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


+49 (0)30 314 - 75902
+49 (0)30 314 - 25839

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


Condition length and complexity for the solution of polynomial systems
Citation key ABBCS-Condition-Length-And-Complexity-For-The-Solution-Of-Polynomial-Systems
Author Diego Armentano and Carlos Beltrán and Peter Bürgisser and Felipe Cucker and Michael Shub
Pages 1401–1422
Year 2016
ISSN 1615-3383
DOI 10.1007/s10208-016-9309-9
Journal Found. Comput. Math.
Volume 16
Number 6
Month 03
Abstract Smale's 17th problem asks for an algorithm which finds an approximate zero of polynomial systems in average polynomial time (see Smale 2000). The main progress on Smale's problem is Beltrán-Pardo (2011) and Bürgisser-Cucker (2010). In this paper we will improve on both approaches and we prove an important intermediate result. Our main results are Theorem 1 on the complexity of a randomized algorithm which improves the result of Beltrán-Pardo (2011), Theorem 2 on the average of the condition number of polynomial systems which improves the estimate found in Bürgisser-Cucker (2010), and Theorem 3 on the complexity of finding a single zero of polynomial systems. This last Theorem is the main result of Bürgisser-Cucker (2010). We give a proof of it relying only on homotopy methods, thus removing the need for the elimination theory methods used in Bürgisser-Cucker (2010). We build on methods developed in Armentano et al. (2015).
Link to publication Link to original publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe