direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments


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

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe