{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T14:04:17Z","timestamp":1776693857424,"version":"3.51.2"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2016,5,18]],"date-time":"2016-05-18T00:00:00Z","timestamp":1463529600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2017,10]]},"DOI":"10.1007\/s10208-016-9319-7","type":"journal-article","created":{"date-parts":[[2016,5,18]],"date-time":"2016-05-18T12:48:23Z","timestamp":1463575703000},"page":"1265-1292","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["A Deterministic Algorithm to Compute Approximate Roots of Polynomial Systems in Polynomial Average Time"],"prefix":"10.1007","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3756-0151","authenticated-orcid":false,"given":"Pierre","family":"Lairez","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,5,18]]},"reference":[{"key":"9319_CR1","doi-asserted-by":"publisher","unstructured":"Michael Shub. Complexity of Bezout\u2019s theorem. VI. Geodesics in the condition (number) metric. In: Found. Comput. Math. 9.2 (2009), pp. 171\u2013178. doi: 10.1007\/s10208-007-9017-6 .","DOI":"10.1007\/s10208-007-9017-6"},{"key":"9319_CR2","doi-asserted-by":"publisher","unstructured":"Michael Shub and Steve Smale. Complexity of B\u00e9zout\u2019s theorem. I. Geometric aspects. In: J. Amer. Math. Soc. 6.2 (1993), pp. 459\u2013501. doi: 10.2307\/2152805 .","DOI":"10.2307\/2152805"},{"key":"9319_CR3","doi-asserted-by":"crossref","unstructured":"Michael Shub and Steve Smale. Complexity of Bezout\u2019s theorem. II. Volumes and probabilities. In: Computational algebraic geometry (Nice, 1992). Vol. 109. Progr. Math. Birkh\u00e4user Boston, Boston, MA, 1993, pp. 267\u2013285.","DOI":"10.1007\/978-1-4612-2752-6_19"},{"key":"9319_CR4","doi-asserted-by":"publisher","unstructured":"Michael Shub and Steve Smale. Complexity of Bezout\u2019s theorem. IV. Probability of success; extensions. In: SIAM J. Numer. Anal. 33.1 (1996), pp. 128\u2013148. doi: 10.1137\/0733008 .","DOI":"10.1137\/0733008"},{"key":"9319_CR5","doi-asserted-by":"publisher","unstructured":"Michael Shub and Steve Smale. Complexity of Bezout\u2019s theorem. V. Polynomial time. In: Theoret. Comput. Sci. 133.1 (1994). Selected papers of the Workshop on Continuous Algorithms and Complexity (Barcelona, 1993), pp. 141\u2013164. doi: 10.1016\/0304-3975(94)90122-8 .","DOI":"10.1016\/0304-3975(94)90122-8"},{"key":"9319_CR6","doi-asserted-by":"publisher","unstructured":"Steve Smale. Newton\u2019s method estimates from data at one point. In: The merging of disciplines: new directions in pure, applied, and computational mathematics (Laramie, Wyo., 1985). Springer, New York, 1986, pp. 185\u2013196. doi: 10.1007\/978-1-4612-4984-9_13 .","DOI":"10.1007\/978-1-4612-4984-9_13"},{"key":"9319_CR7","doi-asserted-by":"publisher","unstructured":"Steve Smale. Mathematical problems for the next century. In: The Mathematical Intelligencer 20.2 (1998), pp. 7\u201315. doi: 10.1007\/BF03025291 .","DOI":"10.1007\/BF03025291"},{"key":"9319_CR8","doi-asserted-by":"publisher","unstructured":"Lenore Blum, Michael Shub, and Steve Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. In: Bull. Amer. Math. Soc. N.S. 21.1 (1989), pp. 1\u201346. doi: 10.1090\/S0273-0979-1989-15750-9 .","DOI":"10.1090\/S0273-0979-1989-15750-9"},{"key":"9319_CR9","doi-asserted-by":"publisher","unstructured":"Carlos Beltr\u00e1n and Luis Miguel Pardo. Fast linear homotopy to find approximate zeros of polynomial systems. In: Found. Comput. Math. 11.1 (2011), pp. 95\u2013129. doi: 10.1007\/s10208-010-9078-9 .","DOI":"10.1007\/s10208-010-9078-9"},{"key":"9319_CR10","doi-asserted-by":"publisher","unstructured":"Peter B\u00fcrgisser and Felipe Cucker. On a problem posed by Steve Smale. In: Ann. of Math. (2) 174.3 (2011), pp. 1785\u20131836. doi: 10.4007\/annals.2011.174.3.8 .","DOI":"10.4007\/annals.2011.174.3.8"},{"key":"9319_CR11","doi-asserted-by":"publisher","unstructured":"Peter B\u00fcrgisser and Felipe Cucker. Condition. The geometry of numerical algorithms. Vol. 349. Grundlehren der Mathematischen Wissenschaften. Springer Berlin Heidelberg, 2013. doi: 10.1007\/978-3-642-38896-5 .","DOI":"10.1007\/978-3-642-38896-5"},{"key":"9319_CR12","doi-asserted-by":"publisher","unstructured":"Carlos Beltr\u00e1n and Luis Miguel Pardo. Smale\u2019s 17th problem: average polynomial time to compute affine and projective solutions. In: J. Amer. Math. Soc. 22.2 (2009), pp. 363\u2013385. doi: 10.1090\/S0894-0347-08-00630-9 .","DOI":"10.1090\/S0894-0347-08-00630-9"},{"key":"9319_CR13","doi-asserted-by":"publisher","unstructured":"Daniel Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing. ACM, New York, 2001, 296\u2013305 (electronic). doi: 10.1145\/380752.380813 .","DOI":"10.1145\/380752.380813"},{"key":"9319_CR14","doi-asserted-by":"publisher","unstructured":"Ir\u00e9n\u00e9e Briquel, Felipe Cucker, Javier Pe\u00f1a, and Vera Roshchina. Fast computation of zeros of polynomial systems with bounded degree under finite-precision. In: Math. Comp. 83.287 (2014), pp. 1279\u20131317. doi: 10.1090\/S0025-5718-2013-02765-2 .","DOI":"10.1090\/S0025-5718-2013-02765-2"},{"key":"9319_CR15","doi-asserted-by":"publisher","unstructured":"Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale. Complexity and real computation. Springer-Verlag, New York, 1998. doi: 10.1007\/978-1-4612-0701-6 .","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"9319_CR16","doi-asserted-by":"publisher","unstructured":"Michael Shub. Some remarks on Bezout\u2019s theorem and complexity theory. In: From Topology to Computation: Proceedings of the Smalefest. Springer, New York, 1993. Chap. 40, pp. 443\u2013455. doi: 10.1007\/978-1-4612-2740-3_40 .","DOI":"10.1007\/978-1-4612-2740-3_40"},{"key":"9319_CR17","doi-asserted-by":"publisher","unstructured":"Masaaki Sibuya. A method for generating uniformly distributed points on N-dimensional spheres. In: Ann. Inst. Statist. Math. 14 (1962), pp. 81\u201385. doi: 10.1007\/BF02868626 .","DOI":"10.1007\/BF02868626"},{"key":"9319_CR18","unstructured":"Diego Armentano, Carlos Beltr\u00e1n, Peter B\u00fcrgisser, Felipe Cucker, and Michael Shub. A stable, polynomial-time algorithm for the eigenpair problem. 2015. arXiv:1505.03290 ."},{"key":"9319_CR19","doi-asserted-by":"publisher","unstructured":"Diego Armentano and Felipe Cucker. A randomized homotopy for the Hermitian eigenpair problem. In: Found. Comput. Math. 15.1 (2015), pp. 281\u2013312. doi: 10.1007\/s10208-014-9217-9 .","DOI":"10.1007\/s10208-014-9217-9"},{"key":"9319_CR20","unstructured":"William Kahan. Accurate eigenvalues of a symmetric tri-diagonal matrix. Tech. rep. CS41. Stanford University, 1966."},{"key":"9319_CR21","doi-asserted-by":"publisher","unstructured":"Walter Baur and Volker Strassen. The complexity of partial derivatives. In: Theoretical Computer Science 22.3 (1983), pp. 317 \u2013330. doi: 10.1016\/0304-3975(83)90110-X .","DOI":"10.1016\/0304-3975(83)90110-X"},{"key":"9319_CR22","doi-asserted-by":"publisher","unstructured":"Diego Armentano, Carlos Beltr\u00e1n, Peter B\u00fcrgisser, Felipe Cucker, and Michael Shub. Condition length and complexity for the solution of polynomial systems. In: Found. Comput. Math. (2016). doi: 10.1007\/s10208-016-9309-9 .","DOI":"10.1007\/s10208-016-9309-9"},{"key":"9319_CR23","doi-asserted-by":"publisher","unstructured":"Carlos Beltr\u00e1n. A continuation method to solve polynomial systems and its complexity. In: Numer. Math. 117.1 (2011), pp. 89\u2013113. doi: 10.1007\/s00211-010-0334-3 .","DOI":"10.1007\/s00211-010-0334-3"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-016-9319-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-016-9319-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-016-9319-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-016-9319-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,7]],"date-time":"2019-09-07T16:37:59Z","timestamp":1567874279000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-016-9319-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,18]]},"references-count":23,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["9319"],"URL":"https:\/\/doi.org\/10.1007\/s10208-016-9319-7","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,5,18]]}}}