{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T14:14:09Z","timestamp":1776867249736,"version":"3.51.2"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,8,4]],"date-time":"2017-08-04T00:00:00Z","timestamp":1501804800000},"content-version":"unspecified","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":[[2018,8]]},"DOI":"10.1007\/s10208-017-9358-8","type":"journal-article","created":{"date-parts":[[2017,8,4]],"date-time":"2017-08-04T19:05:42Z","timestamp":1501873542000},"page":"929-970","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Computing the Homology of Real Projective Sets"],"prefix":"10.1007","volume":"18","author":[{"given":"Felipe","family":"Cucker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Teresa","family":"Krick","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Shub","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,8,4]]},"reference":[{"key":"9358_CR1","doi-asserted-by":"crossref","unstructured":"E.L. Allgower and K. Georg. Numerical Continuation Methods. Springer-Verlag, 1990.","DOI":"10.1007\/978-3-642-61257-2"},{"key":"9358_CR2","unstructured":"D.\u00a0Amelunxen and M.\u00a0Lotz. Average-case complexity without the black swans. To appear at J. Compl. Available at arXiv:1512.09290 , 2016."},{"issue":"1","key":"9358_CR3","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/s10208-005-0208-8","volume":"8","author":"S Basu","year":"2008","unstructured":"S.\u00a0Basu. Computing the top Betti numbers of semialgebraic sets defined by quadratic inequalities in polynomial time. Found. Comput. Math., 8(1):45\u201380, 2008.","journal-title":"Found. Comput. Math."},{"issue":"1","key":"9358_CR4","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s10208-007-9001-1","volume":"8","author":"S Basu","year":"2008","unstructured":"S.\u00a0Basu, R.\u00a0Pollack, and M.-F. Roy. Computing the first Betti number of a semi-algebraic set. Found. Comput. Math., 8(1):97\u2013136, 2008.","journal-title":"Found. Comput. Math."},{"key":"9358_CR5","first-page":"1819","volume-title":"Handbook of Combinatorics","author":"A Bj\u00f6rner","year":"1995","unstructured":"A.\u00a0Bj\u00f6rner. Topological methods. In R.\u00a0Graham, M.\u00a0Grotschel, and L.\u00a0Lovasz, editors, Handbook of Combinatorics, pages 1819\u20131872. North-Holland, Amsterdam, 1995."},{"key":"9358_CR6","doi-asserted-by":"crossref","unstructured":"L.\u00a0Blum, F.\u00a0Cucker, M.\u00a0Shub, and S.\u00a0Smale. Complexity and Real Computation. Springer-Verlag, 1998.","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"9358_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L Blum","year":"1989","unstructured":"L.\u00a0Blum, M.\u00a0Shub, and S.\u00a0Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the Amer. Math. Soc., 21:1\u201346, 1989.","journal-title":"Bulletin of the Amer. Math. Soc."},{"key":"9358_CR8","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/j.jco.2005.11.001","volume":"22","author":"P B\u00fcrgisser","year":"2006","unstructured":"P.\u00a0B\u00fcrgisser and F.\u00a0Cucker. Counting complexity classes for numeric computations II: Algebraic and semialgebraic sets. J. Compl., 22:147\u2013191, 2006.","journal-title":"J. Compl."},{"key":"9358_CR9","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/s10208-007-9006-9","volume":"9","author":"P B\u00fcrgisser","year":"2009","unstructured":"P.\u00a0B\u00fcrgisser and F.\u00a0Cucker. Exotic quantifiers, complexity classes, and complete problems. Found. Comput. Math., 9:135\u2013170, 2009.","journal-title":"Found. Comput. Math."},{"key":"9358_CR10","series-title":"Grundlehren der mathematischen Wissenschaften","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-38896-5","volume-title":"Condition","author":"P B\u00fcrgisser","year":"2013","unstructured":"P.\u00a0B\u00fcrgisser and F.\u00a0Cucker. Condition, volume 349 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag, Berlin, 2013."},{"key":"9358_CR11","first-page":"305","volume":"22","author":"D Cheung","year":"2006","unstructured":"D.\u00a0Cheung and F.\u00a0Cucker. Solving linear programs with finite precision: II. Algorithms. J. Compl., 22:305\u2013335, 2006.","journal-title":"Algorithms. J. Compl."},{"key":"9358_CR12","doi-asserted-by":"crossref","unstructured":"G.E. Collins. Quantifier elimination for real closed fields by cylindrical algebraic deccomposition, volume\u00a033 of Lect. Notes in Comp. Sci., pages 134\u2013183. Springer-Verlag, 1975.","DOI":"10.1007\/3-540-07407-4_17"},{"key":"9358_CR13","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1006\/jcom.1999.0503","volume":"15","author":"F Cucker","year":"1999","unstructured":"F.\u00a0Cucker. Approximate zeros and condition numbers. J. Compl., 15:214\u2013226, 1999.","journal-title":"J. Compl."},{"key":"9358_CR14","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1002\/nla.464","volume":"13","author":"F Cucker","year":"2006","unstructured":"F.\u00a0Cucker, H.\u00a0Diao, and Y.\u00a0Wei. Smoothed analysis of some condition numbers. Numer. Lin. Alg. Appl., 13:71\u201384, 2006.","journal-title":"Numer. Lin. Alg. Appl."},{"key":"9358_CR15","doi-asserted-by":"crossref","first-page":"582","DOI":"10.1016\/j.jco.2008.03.001","volume":"24","author":"F Cucker","year":"2008","unstructured":"F.\u00a0Cucker, T.\u00a0Krick, G.\u00a0Malajovich, and M.\u00a0Wschebor. A numerical algorithm for zero counting. I: Complexity and accuracy. J. Compl., 24:582\u2013605, 2008.","journal-title":"J. Compl."},{"key":"9358_CR16","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1007\/s11784-009-0127-4","volume":"6","author":"F Cucker","year":"2009","unstructured":"F.\u00a0Cucker, T.\u00a0Krick, G.\u00a0Malajovich, and M.\u00a0Wschebor. A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis. J. Fixed Point Theory Appl., 6:285\u2013294, 2009.","journal-title":"J. Fixed Point Theory Appl."},{"key":"9358_CR17","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/j.aam.2011.07.001","volume":"48","author":"F Cucker","year":"2012","unstructured":"F.\u00a0Cucker, T.\u00a0Krick, G.\u00a0Malajovich, and M.\u00a0Wschebor. A numerical algorithm for zero counting. III: Randomization and condition. Adv. Applied Math., 48:215\u2013248, 2012.","journal-title":"Adv. Applied Math."},{"key":"9358_CR18","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1137\/S1052623401386794","volume":"12","author":"F Cucker","year":"2002","unstructured":"F.\u00a0Cucker and J.\u00a0Pe\u00f1a. A primal-dual algorithm for solving polyhedral conic systems with a finite-precision machine. SIAM J. Optim., 12:522\u2013554, 2002.","journal-title":"SIAM J. Optim."},{"key":"9358_CR19","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1145\/300515.300519","volume":"46","author":"F Cucker","year":"1999","unstructured":"F.\u00a0Cucker and S.\u00a0Smale. Complexity estimates depending on condition and round-off error. Journal of the ACM, 46:113\u2013184, 1999.","journal-title":"Journal of the ACM"},{"key":"9358_CR20","doi-asserted-by":"crossref","unstructured":"Carlos D\u2019Andrea, Teresa Krick, and Mart\u00edn Sombra. Heights of varieties in multiprojective spaces and arithmetic Nullstellens\u00e4tze. Ann. Sci. \u00c9c. Norm. Sup\u00e9r. (4), 46(4):549\u2013627 (2013), 2013.","DOI":"10.24033\/asens.2196"},{"key":"9358_CR21","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1090\/S0025-5718-1988-0929546-7","volume":"50","author":"J Demmel","year":"1988","unstructured":"J.\u00a0Demmel. The probability that a numerical analysis problem is difficult. Math. Comp., 50:449\u2013480, 1988.","journal-title":"Math. Comp."},{"key":"9358_CR22","doi-asserted-by":"crossref","unstructured":"H.\u00a0Edelsbrunner and J.L. Harer. Computational topology. American Mathematical Society, Providence, RI, 2010. An introduction.","DOI":"10.1090\/mbk\/069"},{"key":"9358_CR23","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0377-0427(88)90402-5","volume":"22","author":"E Kostlan","year":"1988","unstructured":"E.\u00a0Kostlan. Complexity theory of numerical linear algebra. J. of Computational and Applied Mathematics, 22:219\u2013230, 1988.","journal-title":"J. of Computational and Applied Mathematics"},{"issue":"5","key":"9358_CR24","doi-asserted-by":"crossref","first-page":"1875","DOI":"10.1090\/S0002-9939-2014-12397-5","volume":"143","author":"M Lotz","year":"2015","unstructured":"M.\u00a0Lotz. On the volume of tubular neighborhoods of real algebraic varieties. Proc. Amer. Math. Soc., 143(5):1875\u20131889, 2015.","journal-title":"Proc. Amer. Math. Soc."},{"key":"9358_CR25","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1007\/s00454-008-9053-2","volume":"39","author":"P Niyogi","year":"2008","unstructured":"P.\u00a0Niyogi, S.\u00a0Smale, and S.\u00a0Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete Comput. Geom., 39:419\u2013441, 2008.","journal-title":"Discrete Comput. Geom."},{"key":"9358_CR26","unstructured":"V.\u00a0Noferini and A.\u00a0Townsend. Numerical instability of resultant methods for multidimensional rootfinding. To appear at SIAM J. Num. Analysis. Available at arXiv:1507.00272 ."},{"key":"9358_CR27","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/S0747-7171(10)80003-3","volume":"13","author":"J Renegar","year":"1992","unstructured":"J.\u00a0Renegar. On the computational complexity and geometry of the first-order theory of the reals. Part I. Journal of Symbolic Computation, 13:255\u2013299, 1992.","journal-title":"Journal of Symbolic Computation"},{"key":"9358_CR28","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BF01581690","volume":"65","author":"J Renegar","year":"1994","unstructured":"J.\u00a0Renegar. Some perturbation theory for linear programming. Math. Program., 65:73\u201391, 1994.","journal-title":"Math. Program."},{"key":"9358_CR29","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1137\/0805026","volume":"5","author":"J Renegar","year":"1995","unstructured":"J.\u00a0Renegar. Incorporating condition measures into the complexity theory of linear programming. SIAM J. Optim., 5:506\u2013524, 1995.","journal-title":"SIAM J. Optim."},{"key":"9358_CR30","first-page":"279","volume":"70","author":"J Renegar","year":"1995","unstructured":"J.\u00a0Renegar. Linear programming, complexity theory and elementary functional analysis. Math. Program., 70:279\u2013351, 1995.","journal-title":"Math. Program."},{"issue":"3","key":"9358_CR31","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/j.jco.2007.03.008","volume":"23","author":"P Scheiblechner","year":"2007","unstructured":"P.\u00a0Scheiblechner. On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety. J. Complexity, 23(3):359\u2013379, 2007.","journal-title":"J. Complexity"},{"issue":"5","key":"9358_CR32","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1007\/s10208-012-9123-y","volume":"12","author":"P Scheiblechner","year":"2012","unstructured":"P.\u00a0Scheiblechner. Castelnuovo-Mumford regularity and computing the de Rham cohomology of smooth projective varieties. Found. Comput. Math., 12(5):541\u2013571, 2012.","journal-title":"Found. Comput. Math."},{"key":"9358_CR33","first-page":"459","volume":"6","author":"M Shub","year":"1993","unstructured":"M.\u00a0Shub and S.\u00a0Smale. Complexity of B\u00e9zout\u2019s Theorem I: geometric aspects. Journal of the Amer. Math. Soc., 6:459\u2013501, 1993.","journal-title":"Journal of the Amer. Math. Soc."},{"key":"9358_CR34","doi-asserted-by":"crossref","unstructured":"M.\u00a0Shub and S.\u00a0Smale. Complexity of B\u00e9zout\u2019s Theorem II: volumes and probabilities. In F.\u00a0Eyssette and A.\u00a0Galligo, editors, Computational Algebraic Geometry, volume 109 of Progress in Mathematics, pages 267\u2013285. Birkh\u00e4user, 1993.","DOI":"10.1007\/978-1-4612-2752-6_19"},{"key":"9358_CR35","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1006\/jcom.1993.1002","volume":"9","author":"M Shub","year":"1993","unstructured":"M.\u00a0Shub and S.\u00a0Smale. Complexity of B\u00e9zout\u2019s Theorem III: condition number and packing. Journal of Complexity, 9:4\u201314, 1993.","journal-title":"Journal of Complexity"},{"key":"9358_CR36","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/0304-3975(94)90122-8","volume":"133","author":"M Shub","year":"1994","unstructured":"M.\u00a0Shub and S.\u00a0Smale. Complexity of B\u00e9zout\u2019s Theorem V: polynomial time. Theoret. Comp. Sci., 133:141\u2013164, 1994.","journal-title":"Theoret. Comp. Sci."},{"key":"9358_CR37","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1137\/0733008","volume":"33","author":"M Shub","year":"1996","unstructured":"M.\u00a0Shub and S.\u00a0Smale. Complexity of B\u00e9zout\u2019s Theorem IV: probability of success; extensions. SIAM J. of Numer. Anal., 33:128\u2013148, 1996.","journal-title":"SIAM J. of Numer. Anal."},{"key":"9358_CR38","doi-asserted-by":"crossref","unstructured":"S.\u00a0Smale. Newton\u2019s method estimates from data at one point. In R.\u00a0Ewing, K.\u00a0Gross, and C.\u00a0Martin, editors, The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics. Springer-Verlag, 1986.","DOI":"10.1007\/978-1-4612-4984-9_13"},{"key":"9358_CR39","doi-asserted-by":"crossref","unstructured":"A.\u00a0Storjohann. Nearly optimal algorithms for computing Smith normal forms of integer matrices. In Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC\u201996), pages 267\u2013274. ACM Press, 1996.","DOI":"10.1145\/236869.237084"},{"key":"9358_CR40","doi-asserted-by":"crossref","unstructured":"H.R. W\u00fcthrich. Ein Entscheidungsverfahren f\u00fcr die Theorie der reell-abgeschlossenen K\u00f6rper. In E.\u00a0Specker and V.\u00a0Strassen, editors, Komplexit\u00e4t von Entscheidungsproblemen, volume\u00a043 of Lect. Notes in Comp. Sci., pages 138\u2013162. Springer-Verlag, 1976.","DOI":"10.1007\/3-540-07805-3_10"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-017-9358-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-017-9358-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-017-9358-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,31]],"date-time":"2022-07-31T20:27:38Z","timestamp":1659299258000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-017-9358-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,4]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,8]]}},"alternative-id":["9358"],"URL":"https:\/\/doi.org\/10.1007\/s10208-017-9358-8","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,4]]}}}