@article{ABBCS-Condition-Length-And-Complexity-For-The-Solution-Of-Polynomial-Systems,
Title = {Condition length and complexity for the solution of polynomial systems},
Author = {Diego Armentano and Carlos Beltr\´an and Peter B\"urgisser and Felipe Cucker and Michael Shub},
Pages = {1401--1422},
Year = {2016},
Issn = {1615-3383},
Doi = {10.1007/s10208-016-9309-9},
Journal = {Found. Comput. Math.},
Volume = {16},
Number = {6},
Month = {03},
Abstract = {Smale's 17th problem asks for an algorithm which finds an approximate zero of polynomial systems in average polynomial time (see Smale 2000). The main progress on Smale's problem is Beltr\´an-Pardo (2011) and B\"urgisser-Cucker (2010). In this paper we will improve on both approaches and we prove an important intermediate result. Our main results are Theorem 1 on the complexity of a randomized algorithm which improves the result of Beltr\´an-Pardo (2011), Theorem 2 on the average of the condition number of polynomial systems which improves the estimate found in B\"urgisser-Cucker (2010), and Theorem 3 on the complexity of finding a single zero of polynomial systems. This last Theorem is the main result of B\"urgisser-Cucker (2010). We give a proof of it relying only on homotopy methods, thus removing the need for the elimination theory methods used in B\"urgisser-Cucker (2010). We build on methods developed in Armentano et al. (2015).},
Url = {http://arxiv.org/abs/1507.03896},
Url2 = {http://dx.doi.org/10.1007/s10208-016-9309-9}
}