TU Berlin

Fachgebiet Algorithmische AlgebraPublications

Inhalt des Dokuments

zur Navigation

Search for Publication

Suche nach Publikationen

All Publications

A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time
Zitatschlüssel L-A-Deterministic-Algorithm-To-Compute-Approximate-Roots-Of-Polynomial-Systems-In-Polynomial-Average-Time
Autor Pierre Lairez
Jahr 2015
Monat 10
Notiz To appear in Foundations of computational mathematics (2016), 23 pages.
Zusammenfassung We describe a deterministic algorithm that computes an approximate root of n complex polynomial equations in n unknowns in average polynomial time with respect to the size of the input, in the Blum-Shub-Smale model with square root. It rests upon a derandomization of an algorithm of Beltrán and Pardo and gives a deterministic affirmative answer to Smale's 17th problem. The main idea is to make use of the randomness contained in the input itself.
Link zur Publikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe