TU Berlin

Fachgebiet Algorithmische AlgebraDr. Pierre Lairez

Page Content

to Navigation

Ehemalige Mitarbeiter

Dr. Pierre Lairez


INRIA Saclay Île-de-France, Bât. Alan Turing
1 rue Honoré d'Estienne d'Orves
Campus de l'École polytechnique
91120 Palaiseau
Persönliche Homepage

Publikationen in der Arbeitsgruppe

A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time
Citation key L-A-Deterministic-Algorithm-To-Compute-Approximate-Roots-Of-Polynomial-Systems-In-Polynomial-Average-Time
Author Pierre Lairez
Year 2015
Month 10
Note To appear in Foundations of computational mathematics (2016), 23 pages.
Abstract 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 to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe