TU Berlin

Fachgebiet Algorithmische AlgebraIn Proceedings

Page Content

to Navigation

There is no English translation for this web page.

In Proceedings

Solving Polynomial Equations in Smoothed Polynomial Time and a Near Solution to Smale's 17th Problem
Citation key BC-Solving-Polynomial-Equations-In-Smoothed-Polynomial-Time-And-A-Near-Solution-To-Smales-17Th-Problem
Author Peter Bürgisser and Felipe Cucker
Title of Book In Proceedings STOC 2010
Pages 503-512
Year 2010
Abstract The 17th of the problems proposed by Steve Smale for the 21st century asks for the existence of a deterministic algorithm computing an approximate solution of a system of $n$ complex polynomials in $n$ unknowns in time polynomial, on the average, in the size $N$ of the input system. A partial solution to this problem was given by Carlos Beltran and Luis Miguel Pardo who exhibited a randomized algorithm doing so. In this paper we further extend this result in several directions. Firstly, we exhibit a linear homotopy algorithm that efficiently implements a non-constructive idea of Mike Shub. This algorithm is then used in a randomized algorithm, call it LV, a la Beltran-Pardo. Secondly, we perform a smoothed analysis (in the sense of Spielman and Teng) of algorithm LV and prove that its smoothed complexity is polynomial in the input size and $s^-1$, where $s$ controls the size of of the random perturbation of the input systems. Thirdly, we perform a condition-based analysis of LV. That is, we give a bound, for each system $f$, of the expected running time of LV with input $f$. In addition to its dependence on $N$ this bound also depends on the condition of $f$. Fourthly, and to conclude, we return to Smale's 17th problem as originally formulated for deterministic algorithms. We exhibit such an algorithm and show that its average complexity is $N^O(łogłog N)$. This is nearly a solution to Smale's 17th problem.
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe