{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:19:48Z","timestamp":1742912388287,"version":"3.40.3"},"publisher-location":"Cham","reference-count":43,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030229955"},{"type":"electronic","value":"9783030229962"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"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":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-22996-2_1","type":"book-chapter","created":{"date-parts":[[2019,7,3]],"date-time":"2019-07-03T23:02:56Z","timestamp":1562194976000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Recent Advances in the Computation of the Homology of Semialgebraic Sets"],"prefix":"10.1007","author":[{"given":"Felipe","family":"Cucker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,6,19]]},"reference":[{"key":"1_CR1","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1016\/j.jco.2016.12.002","volume":"41","author":"D Amelunxen","year":"2017","unstructured":"Amelunxen, D., Lotz, M.: Average-case complexity without the black swans. J. Complexity 41, 82\u2013101 (2017)","journal-title":"J. Complexity"},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"Basu, S.: On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets. In: Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996), pp. 408\u2013417. ACM, New York (1996)","DOI":"10.1145\/237814.237988"},{"issue":"10","key":"1_CR3","doi-asserted-by":"publisher","first-page":"1125","DOI":"10.1016\/j.jsc.2006.07.001","volume":"41","author":"S Basu","year":"2006","unstructured":"Basu, S.: Computing the first few Betti numbers of semi-algebraic sets in single exponential time. J. Symbolic Comput. 41(10), 1125\u20131154 (2006)","journal-title":"J. Symbolic Comput."},{"key":"1_CR4","doi-asserted-by":"publisher","first-page":"1002","DOI":"10.1145\/235809.235813","volume":"43","author":"S Basu","year":"1996","unstructured":"Basu, S., Pollack, R., Roy, M.F.: On the combinatorial and algebraic complexity of quantifier elimination. J. ACM 43, 1002\u20131045 (1996)","journal-title":"J. ACM"},{"key":"1_CR5","first-page":"55","volume":"33","author":"S Basu","year":"1999","unstructured":"Basu, S., Pollack, R., Roy, M.F.: Computing roadmaps of semi-algebraic sets on a variety. J. AMS 33, 55\u201382 (1999)","journal-title":"J. AMS"},{"key":"1_CR6","series-title":"Algorithms and Computation in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-33099-2","volume-title":"Algorithms in real algebraic geometry","author":"S Basu","year":"2006","unstructured":"Basu, S., Pollack, R., Roy, M.F.: Algorithms in real algebraic geometry. Algorithms and Computation in Mathematics, vol. 10, 2nd edn. Springer, Berlin (2006)","edition":"2"},{"key":"1_CR7","unstructured":"Benedetti, R., Risler, J.J.: Real Algebraic and Semi-algebraic Sets, Hermann (1990)"},{"key":"1_CR8","series-title":"Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge\/A Series of Modern Surveys in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03718-8","volume-title":"Real Algebraic Geometry","author":"J Bochnak","year":"1998","unstructured":"Bochnak, J., Coste, M., Roy, M.F.: Real Algebraic Geometry. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge\/A Series of Modern Surveys in Mathematics, vol. 36. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/978-3-662-03718-8. Translated from the 1987 French original, Revised by the authors"},{"key":"1_CR9","series-title":"Grundlehren der mathematischen Wissenschaften","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38896-5","volume-title":"Condition","author":"P B\u00fcrgisser","year":"2013","unstructured":"B\u00fcrgisser, P., Cucker, F.: Condition. Grundlehren der mathematischen Wissenschaften, vol. 349. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38896-5"},{"issue":"1","key":"1_CR10","doi-asserted-by":"publisher","first-page":"5:1","DOI":"10.1145\/3275242","volume":"66","author":"P B\u00fcrgisser","year":"2019","unstructured":"B\u00fcrgisser, P., Cucker, F., Lairez, P.: Computing the homology of basic semialgebraic sets in weakly exponential time. J. ACM 66(1), 5:1\u20135:30 (2019)","journal-title":"J. ACM"},{"key":"1_CR11","doi-asserted-by":"publisher","first-page":"1559","DOI":"10.1090\/S0025-5718-08-02060-7","volume":"77","author":"P B\u00fcrgisser","year":"2008","unstructured":"B\u00fcrgisser, P., Cucker, F., Lotz, M.: The probability that a slightly perturbed numerical analysis problem is difficult. Math. Comput. 77, 1559\u20131583 (2008)","journal-title":"Math. Comput."},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"B\u00fcrgisser, P., Cucker, F., Tonelli-Cueto, J.: Computing the homology of semialgebraic sets. I: Lax formulas. Found. Comput. Math. arXiv:1807.06435 (2018)","DOI":"10.1007\/s10208-019-09418-y"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"B\u00fcrgisser, P., Cucker, F., Tonelli-Cueto, J.: Computing the homology of semialgebraic sets. II: Arbitrary formulas (2019). preprint","DOI":"10.1007\/s10208-019-09418-y"},{"issue":"5","key":"1_CR14","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1093\/comjnl\/36.5.504","volume":"36","author":"J Canny","year":"1993","unstructured":"Canny, J.: Computing roadmaps of general semi-algebraic sets. Comput. J. 36(5), 504\u2013514 (1993)","journal-title":"Comput. J."},{"issue":"4","key":"1_CR15","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01614146","volume":"2","author":"J Canny","year":"1992","unstructured":"Canny, J., Grigorev, D., Vorobjov, N.: Finding connected components of a semialgebraic set in subexponential time. Appl. Algebra Eng. Commun. Comput. 2(4), 217\u2013238 (1992)","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"key":"1_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1007\/3-540-07407-4_17","volume-title":"Automata Theory and Formal Languages 2nd GI Conference Kaiserslautern","author":"GE Collins","year":"1975","unstructured":"Collins, G.E.: Quantifier elimination for real closed fields by cylindrical algebraic decompostion. In: Brakhage, H. (ed.) GI-Fachtagung 1975. LNCS, vol. 33, pp. 134\u2013183. Springer, Heidelberg (1975). https:\/\/doi.org\/10.1007\/3-540-07407-4_17"},{"key":"1_CR17","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1006\/jcom.1999.0503","volume":"15","author":"F Cucker","year":"1999","unstructured":"Cucker, F.: Approximate zeros and condition numbers. J. Complexity 15, 214\u2013226 (1999)","journal-title":"J. Complexity"},{"key":"1_CR18","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1007\/s10208-017-9358-8","volume":"18","author":"F Cucker","year":"2018","unstructured":"Cucker, F., Krick, T., Shub, M.: Computing the homology of real projective sets. Found. Comp. Math. 18, 929\u2013970 (2018)","journal-title":"Found. Comp. Math."},{"key":"1_CR19","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1145\/300515.300519","volume":"46","author":"F Cucker","year":"1999","unstructured":"Cucker, F., Smale, S.: Complexity estimates depending on condition and round-off error. J. ACM 46, 113\u2013184 (1999)","journal-title":"J. ACM"},{"key":"1_CR20","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1090\/S0025-5718-1988-0929546-7","volume":"50","author":"J Demmel","year":"1988","unstructured":"Demmel, J.: The probability that a numerical analysis problem is difficult. Math. Comput. 50, 449\u2013480 (1988)","journal-title":"Math. Comput."},{"issue":"1","key":"1_CR21","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1112\/jlms\/jdp006","volume":"80","author":"A Gabrielov","year":"2009","unstructured":"Gabrielov, A., Vorobjov, N.: Approximation of definable sets by compact families, and upper bounds on homotopy and homology. J. Lond. Math. Soc. 80(1), 35\u201354 (2009)","journal-title":"J. Lond. Math. Soc."},{"key":"1_CR22","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1090\/S0002-9939-1951-0041539-X","volume":"2","author":"H Goldstine","year":"1951","unstructured":"Goldstine, H., von Neumann, J.: Numerical inverting matrices of high order, II. Proc. AMS 2, 188\u2013202 (1951)","journal-title":"Proc. AMS"},{"key":"1_CR23","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/S0747-7171(88)80006-3","volume":"5","author":"D Grigoriev","year":"1988","unstructured":"Grigoriev, D.: Complexity of deciding Tarski algebra. J. Symbolic Comput. 5, 65\u2013108 (1988)","journal-title":"J. Symbolic Comput."},{"key":"1_CR24","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/S0747-7171(88)80005-1","volume":"5","author":"D Grigoriev","year":"1988","unstructured":"Grigoriev, D., Vorobjov, N.: Solving systems of polynomial inequalities in subexponential time. J. Symbolic Comput. 5, 37\u201364 (1988)","journal-title":"J. Symbolic Comput."},{"key":"1_CR25","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01202001","volume":"2","author":"D Grigoriev","year":"1992","unstructured":"Grigoriev, D., Vorobjov, N.: Counting connected components of a semialgebraic set in subexponential time. Comput. Complexity 2, 133\u2013186 (1992)","journal-title":"Comput. Complexity"},{"key":"1_CR26","volume-title":"Algebraic Topology","author":"A Hatcher","year":"2002","unstructured":"Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002)"},{"key":"1_CR27","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/978-1-4612-2628-4_28","volume-title":"Algebraic Geometry and its Applications","author":"J Heintz","year":"1994","unstructured":"Heintz, J., Roy, M.F., Solerno, P.: Single exponential path finding in semi-algebraic sets II: the general case. In: Bajaj, C. (ed.) Algebraic Geometry and its Applications, pp. 449\u2013465. Springer, New York (1994). https:\/\/doi.org\/10.1007\/978-1-4612-2628-4_28"},{"key":"1_CR28","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1006\/jcom.1999.0502","volume":"15","author":"P Koiran","year":"1999","unstructured":"Koiran, P.: The real dimension problem is $${\\sf N}P_{\\mathbb{R}}$$-complete. J. Complexity 15, 227\u2013238 (1999)","journal-title":"J. Complexity"},{"key":"1_CR29","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0377-0427(88)90402-5","volume":"22","author":"E Kostlan","year":"1988","unstructured":"Kostlan, E.: Complexity theory of numerical linear algebra. J. Comput. Appl. Math. 22, 219\u2013230 (1988)","journal-title":"J. Comput. Appl. Math."},{"key":"1_CR30","doi-asserted-by":"publisher","first-page":"1021","DOI":"10.1090\/S0002-9904-1947-08909-6","volume":"53","author":"J von Neumann","year":"1947","unstructured":"von Neumann, J., Goldstine, H.: Numerical inverting matrices of high order. Bull. AMS 53, 1021\u20131099 (1947)","journal-title":"Bull. AMS"},{"key":"1_CR31","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/s00454-008-9053-2","volume":"39","author":"P Niyogi","year":"2008","unstructured":"Niyogi, P., Smale, S., Weinberger, S.: Finding the homology of submanifolds with high confidence from random samples. Discrete Comput. Geom. 39, 419\u2013441 (2008)","journal-title":"Discrete Comput. Geom."},{"key":"1_CR32","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0747-7171(10)80003-3","volume":"13","author":"J Renegar","year":"1992","unstructured":"Renegar, J.: On the computational complexity and geometry of the first-order theory of the reals. Part I. J. Symbolic Comput. 13, 255\u2013299 (1992)","journal-title":"J. Symbolic Comput."},{"key":"1_CR33","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BF01581690","volume":"65","author":"J Renegar","year":"1994","unstructured":"Renegar, J.: Some perturbation theory for linear programming. Math. Program. 65, 73\u201391 (1994)","journal-title":"Math. Program."},{"key":"1_CR34","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1137\/0805026","volume":"5","author":"J Renegar","year":"1995","unstructured":"Renegar, J.: Incorporating condition measures into the complexity theory of linear programming. SIAM J. Optim. 5, 506\u2013524 (1995)","journal-title":"SIAM J. Optim."},{"key":"1_CR35","first-page":"279","volume":"70","author":"J Renegar","year":"1995","unstructured":"Renegar, J.: Linear programming, complexity theory and elementary functional analysis. Math. Program. 70, 279\u2013351 (1995)","journal-title":"Math. Program."},{"key":"1_CR36","first-page":"459","volume":"6","author":"M Shub","year":"1993","unstructured":"Shub, M., Smale, S.: Complexity of B\u00e9zout\u2019s theorem I: geometric aspects. J. AMS 6, 459\u2013501 (1993)","journal-title":"J. AMS"},{"key":"1_CR37","doi-asserted-by":"crossref","unstructured":"Smale, S.: Complexity theory and numerical analysis. In: Iserles, A. (ed.) Acta Numerica, pp. 523\u2013551. Cambridge University Press (1997)","DOI":"10.1017\/S0962492900002774"},{"issue":"10","key":"1_CR38","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1145\/1562764.1562785","volume":"52","author":"D Spielman","year":"2009","unstructured":"Spielman, D., Teng, S.H.: Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Commun. ACM 52(10), 77\u201384 (2009)","journal-title":"Commun. ACM"},{"key":"1_CR39","doi-asserted-by":"crossref","DOI":"10.1525\/9780520348097","volume-title":"A Decision Method for Elementary Algebra and Geometry","author":"A Tarski","year":"1951","unstructured":"Tarski, A.: A Decision Method for Elementary Algebra and Geometry. University of California Press, Berkeley (1951)"},{"key":"1_CR40","first-page":"230","volume":"S2\u201342","author":"A Turing","year":"1936","unstructured":"Turing, A.: On computable numbers, with an application to the Entscheidungsproblem. Proc. London Math. Soc. S2\u201342, 230\u2013265 (1936)","journal-title":"Proc. London Math. Soc."},{"key":"1_CR41","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1093\/qjmam\/1.1.287","volume":"1","author":"A Turing","year":"1948","unstructured":"Turing, A.: Rounding-off errors in matrix processes. Quart. J. Mech. Appl. Math. 1, 287\u2013308 (1948)","journal-title":"Quart. J. Mech. Appl. Math."},{"key":"1_CR42","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1145\/321637.321638","volume":"18","author":"J Wilkinson","year":"1971","unstructured":"Wilkinson, J.: Some comments from a numerical analyst. J. ACM 18, 137\u2013147 (1971)","journal-title":"J. ACM"},{"key":"1_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/3-540-07805-3_10","volume-title":"Komplexit\u00e4t von Entscheidungsproblemen Ein Seminar","author":"HR W\u00fcthrich","year":"1976","unstructured":"W\u00fcthrich, H.R.: Ein Entscheidungsverfahren f\u00fcr die Theorie der reell-abgeschlossenen K\u00f6rper. In: Strassen, V., Specker, E. (eds.) Komplexit\u00e4t von Entscheidungsproblemen Ein Seminar. LNCS, vol. 43, pp. 138\u2013162. Springer, Heidelberg (1976). https:\/\/doi.org\/10.1007\/3-540-07805-3_10"}],"container-title":["Lecture Notes in Computer Science","Computing with Foresight and Industry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-22996-2_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T11:19:04Z","timestamp":1709810344000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-22996-2_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030229955","9783030229962"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-22996-2_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"19 June 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CiE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Computability in Europe","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Durham","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 July 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 July 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cie2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/community.dur.ac.uk\/cie.2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"35","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"20","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"57% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Also included are 7 invited papers","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}