A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time

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.

References in corpus (2)

• Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric
• A stable, polynomial-time algorithm for the eigenpair problem

Cited by in corpus (9)

• Estimation under group actions: recovering orbits from invariants
• Computing the Homology of Semialgebraic Sets I: Lax Formulas
• Algebraic compressed sensing
• Probabilistic Condition Number Estimates For Real Polynomial Systems I: A Broader Family Of Distributions
• A sequence of polynomials with optimal condition number
• The average condition number of most tensor rank decomposition problems is infinite
• Complexity of Sparse Polynomial Solving 2: Renormalization
• Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems
• Rigid continuation paths II. Structured polynomial systems