{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T14:15:22Z","timestamp":1776867322457,"version":"3.51.2"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,12,16]],"date-time":"2018-12-16T00:00:00Z","timestamp":1544918400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,2,28]]},"abstract":"<jats:p>We describe and analyze an algorithm for computing the homology (Betti numbers and torsion coefficients) of basic semialgebraic sets that works in weak exponential time. That is, of a set of exponentially small measure in the space of data, the cost of the algorithm is exponential in the size of the data. All algorithms previously proposed for this problem have a complexity that is doubly exponential (and this is so for almost all data).<\/jats:p>","DOI":"10.1145\/3275242","type":"journal-article","created":{"date-parts":[[2018,12,17]],"date-time":"2018-12-17T13:17:16Z","timestamp":1545052636000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Computing the Homology of Basic Semialgebraic Sets in Weak Exponential Time"],"prefix":"10.1145","volume":"66","author":[{"given":"Peter","family":"B\u00fcrgisser","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Felipe","family":"Cucker","sequence":"additional","affiliation":[{"name":"City University of Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"Lairez","sequence":"additional","affiliation":[{"name":"Inria, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,12,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2016.12.002"},{"key":"e_1_2_1_2_1","volume-title":"Surveys on Discrete and Computational Geometry. Contemp. Math.","author":"Basu S.","unstructured":"S. Basu . 2008. Algorithmic semi-algebraic geometry and topology\u2014recent progress and open problems . In Surveys on Discrete and Computational Geometry. Contemp. Math. , Vol. 453 . American Mathematical Society , Providence, RI , 139--212. S. Basu. 2008. Algorithmic semi-algebraic geometry and topology\u2014recent progress and open problems. In Surveys on Discrete and Computational Geometry. Contemp. Math., Vol. 453. American Mathematical Society, Providence, RI, 139--212."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2794645.3115525"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1090\/S0894-0347-99-00311-2","article-title":"Computing roadmaps of semi-algebraic sets on a variety","volume":"33","author":"Basu S.","year":"1999","unstructured":"S. Basu , R. Pollack , and M.-F. Roy . 1999 . Computing roadmaps of semi-algebraic sets on a variety . J. Am. Math. Soc. 33 (1999), 55 -- 82 . S. Basu, R. Pollack, and M.-F. Roy. 1999. Computing roadmaps of semi-algebraic sets on a variety. J. Am. Math. Soc. 33 (1999), 55--82.","journal-title":"J. Am. Math. Soc."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10958-006-0111-0"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060636"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/235809.235813"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-014-9212-1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2006.07.001"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237988"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2794645.3115526"},{"key":"e_1_2_1_12_1","volume-title":"Handbook of Combinatorics","author":"Bj\u00f6rner A.","year":"1819","unstructured":"A. Bj\u00f6rner . 1995. Topological methods . In Handbook of Combinatorics , R. Graham, M. Grotschel, and L. Lovasz (Eds.). North-Holland , Amsterdam , 1819 --1872. A. Bj\u00f6rner. 1995. Topological methods. In Handbook of Combinatorics, R. Graham, M. Grotschel, and L. Lovasz (Eds.). North-Holland, Amsterdam, 1819--1872."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1989-15750-9"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206054"},{"key":"e_1_2_1_15_1","volume-title":"Functions of a Real Variable","author":"Bourbaki Nicolas","unstructured":"Nicolas Bourbaki . 2004. Functions of a Real Variable . Springer-Verlag , Berlin . Nicolas Bourbaki. 2004. Functions of a Real Variable. Springer-Verlag, Berlin."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.2307\/1970177"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"P. B\u00fcrgisser M. Clausen and A. Shokrollahi. 1996. Algebraic Complexity Theory. Grundlehren der mathematischen Wissenschaften Vol. 315. Springer-Verlag.  P. B\u00fcrgisser M. Clausen and A. Shokrollahi. 1996. Algebraic Complexity Theory. Grundlehren der mathematischen Wissenschaften Vol. 315. Springer-Verlag.","DOI":"10.1007\/978-3-662-03338-8"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"P. B\u00fcrgisser and F. Cucker. 2013. Condition. Grundlehren der mathematischen Wissenschaften Vol. 349. Springer-Verlag Berlin.  P. B\u00fcrgisser and F. Cucker. 2013. Condition. Grundlehren der mathematischen Wissenschaften Vol. 349. Springer-Verlag Berlin.","DOI":"10.1007\/978-3-642-38896-5"},{"key":"e_1_2_1_19_1","volume-title":"Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (Lecture Notes in Computer Science)","author":"Canny J. F.","unstructured":"J. F. Canny . 1991. Computing roadmaps of general semi-algebraic sets . In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (Lecture Notes in Computer Science) . Springer , Berlin, Heidelberg , 94--107. J. F. Canny. 1991. Computing roadmaps of general semi-algebraic sets. In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (Lecture Notes in Computer Science). Springer, Berlin, Heidelberg, 94--107."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01614146"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/36.5.504"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/3115960.3116066"},{"key":"e_1_2_1_23_1","volume-title":"Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Deccomposition. Lect. Notes Comp. Sci","author":"Collins G.E.","unstructured":"G.E. Collins . 1975. Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Deccomposition. Lect. Notes Comp. Sci ., Vol. 33 . Springer-Verlag , 134--183. G.E. Collins. 1975. Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Deccomposition. Lect. Notes Comp. Sci., Vol. 33. Springer-Verlag, 134--183."},{"key":"e_1_2_1_24_1","first-page":"180","article-title":"A new proof of Brown\u2019s Collaring theorem","volume":"27","author":"Connelly Robert","year":"1971","unstructured":"Robert Connelly . 1971 . A new proof of Brown\u2019s Collaring theorem . Proc. Am. Math. Soc. 27 , 1 (1971), 180 . Robert Connelly. 1971. A new proof of Brown\u2019s Collaring theorem. Proc. Am. Math. Soc. 27, 1 (1971), 180.","journal-title":"Proc. Am. Math. Soc."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1999.0503"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2008.03.001"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11784-009-0127-4"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/300515.300519"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-017-9358-8"},{"key":"e_1_2_1_30_1","volume-title":"Z\u00e9ros et La M\u00e9thode de Newton. Math\u00e9matiques 8 Applications","author":"Dedieu Jean-Pierre","unstructured":"Jean-Pierre Dedieu . 2006. Points Fixes , Z\u00e9ros et La M\u00e9thode de Newton. Math\u00e9matiques 8 Applications , Vol. 54 . Springer . Jean-Pierre Dedieu. 2006. Points Fixes, Z\u00e9ros et La M\u00e9thode de Newton. Math\u00e9matiques 8 Applications, Vol. 54. Springer."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574053"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/142675.142688"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/174462.156635"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1959-0110078-1"},{"key":"e_1_2_1_35_1","volume-title":"Zelevinsky","author":"Gelfand Israel M.","year":"1994","unstructured":"Israel M. Gelfand , Mikhail M. Kapranov , and Andrei V . Zelevinsky . 1994 . Discriminants, Resultants , and Multidimensional Determinants. Birkh\u00e4user Boston Inc ., Boston, MA. Israel M. Gelfand, Mikhail M. Kapranov, and Andrei V. Zelevinsky. 1994. Discriminants, Resultants, and Multidimensional Determinants. Birkh\u00e4user Boston Inc., Boston, MA."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/0710036"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(88)80005-1"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01202001"},{"key":"e_1_2_1_39_1","volume-title":"Algebraic Geometry and Its Applications","author":"Heintz Joos","unstructured":"Joos Heintz , Marie-Fran\u00e7oise Roy , and Pablo Solern\u00f3 . 1994. Single exponential path finding in semi-algebraic sets. II. The general case . In Algebraic Geometry and Its Applications . Springer , New York , 449--465. Joos Heintz, Marie-Fran\u00e7oise Roy, and Pablo Solern\u00f3. 1994. Single exponential path finding in semi-algebraic sets. II. The general case. In Algebraic Geometry and Its Applications. Springer, New York, 449--465."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.049.044"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1999.0502"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-0427(88)90402-5"},{"key":"e_1_2_1_43_1","unstructured":"Pierre Lairez. 2017. Rigid Continuation Paths I. Quasilinear Average Complexity for Solving Polynomial Systems. arxiv:1711.03420  Pierre Lairez. 2017. Rigid Continuation Paths I. Quasilinear Average Complexity for Solving Polynomial Systems. arxiv:1711.03420"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0096-3003(87)90063-4"},{"key":"e_1_2_1_45_1","volume-title":"Complex Projective Varieties","author":"Mumford D.","unstructured":"D. Mumford . 1976. Algebraic Geometry I , Complex Projective Varieties . Springer-Verlag . D. Mumford. 1976. Algebraic Geometry I, Complex Projective Varieties. Springer-Verlag."},{"key":"e_1_2_1_46_1","volume-title":"Theory of Functions of a Real Variable","author":"Natanson I. P.","unstructured":"I. P. Natanson . 1955. Theory of Functions of a Real Variable . Frederick Ungar Publishing Co. , New York, NY . I. P. Natanson. 1955. Theory of Functions of a Real Variable. Frederick Ungar Publishing Co., New York, NY."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1947-08909-6"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/3116660.3117013"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(10)80003-3"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2996450"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-012-9123-y"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2007.03.008"},{"key":"e_1_2_1_53_1","volume-title":"Basic Algebraic Geometry. 1: Varieties in Projective Space (2 Ed.)","author":"Shafarevich I. R.","unstructured":"I. R. Shafarevich . 1994. Basic Algebraic Geometry. 1: Varieties in Projective Space (2 Ed.) . Springer-Verlag . I. R. Shafarevich. 1994. Basic Algebraic Geometry. 1: Varieties in Projective Space (2 Ed.). Springer-Verlag."},{"key":"e_1_2_1_54_1","first-page":"459","article-title":"Complexity of B\u00e9zout\u2019s theorem I: Geometric aspects","volume":"6","author":"Shub M.","year":"1993","unstructured":"M. Shub and S. Smale . 1993 . Complexity of B\u00e9zout\u2019s theorem I: Geometric aspects . J. Am. Math. Soc. 6 (1993), 459 -- 501 . M. Shub and S. Smale. 1993. Complexity of B\u00e9zout\u2019s theorem I: Geometric aspects. J. Am. Math. Soc. 6 (1993), 459--501.","journal-title":"J. Am. Math. Soc."},{"key":"e_1_2_1_55_1","volume-title":"II: Volumes and probabilities. In Computational Algebraic Geometry (Progress in Mathematics)","author":"Shub M.","year":"1993","unstructured":"M. Shub and S. Smale . 1993 . Complexity of B\u00e9zout\u2019s theorem II: Volumes and probabilities. In Computational Algebraic Geometry (Progress in Mathematics) , F. Eyssette and A. Galligo (Eds.), Vol. 109 . Birkh\u00e4user , 267--285. M. Shub and S. Smale. 1993. Complexity of B\u00e9zout\u2019s theorem II: Volumes and probabilities. In Computational Algebraic Geometry (Progress in Mathematics), F. Eyssette and A. Galligo (Eds.), Vol. 109. Birkh\u00e4user, 267--285."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1993.1002"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/0733008"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90122-8"},{"key":"e_1_2_1_59_1","volume-title":"Complexity theory and numerical analysis","author":"Smale S.","unstructured":"S. Smale . 1997. Complexity theory and numerical analysis . In Acta Numerica, A. Iserles (Ed.). Cambridge University Press , 523--551. S. Smale. 1997. Complexity theory and numerical analysis. In Acta Numerica, A. Iserles (Ed.). Cambridge University Press, 523--551."},{"key":"e_1_2_1_60_1","volume-title":"The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics","author":"Smale Steve","unstructured":"Steve Smale . 1986. Newton\u2019s method estimates from data at one point . In The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics . Springer , New York , 185--196. Steve Smale. 1986. Newton\u2019s method estimates from data at one point. In The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics. Springer, New York, 185--196."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1093\/qjmam\/1.1.287"},{"key":"e_1_2_1_62_1","volume-title":"Komplexit\u00e4t von Entscheidungsproblemen (Lect. Notes Comp. Sci.)","author":"W\u00fcthrich H. R.","unstructured":"H. R. W\u00fcthrich . 1976. Ein Entscheidungsverfahren f\u00fcr die Theorie der reell-abgeschlossenen K\u00f6rper . In Komplexit\u00e4t von Entscheidungsproblemen (Lect. Notes Comp. Sci.) , E. Specker and V. Strassen (Eds.), Vol. 43 . Springer-Verlag , 138--162. H. R. W\u00fcthrich. 1976. Ein Entscheidungsverfahren f\u00fcr die Theorie der reell-abgeschlossenen K\u00f6rper. In Komplexit\u00e4t von Entscheidungsproblemen (Lect. Notes Comp. Sci.), E. Specker and V. Strassen (Eds.), Vol. 43. Springer-Verlag, 138--162."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3275242","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3275242","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:44:38Z","timestamp":1750207478000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3275242"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,16]]},"references-count":62,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,2,28]]}},"alternative-id":["10.1145\/3275242"],"URL":"https:\/\/doi.org\/10.1145\/3275242","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,12,16]]},"assertion":[{"value":"2017-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}