{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T06:14:52Z","timestamp":1777616092792,"version":"3.51.4"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,8,2]],"date-time":"2021-08-02T00:00:00Z","timestamp":1627862400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,8,2]],"date-time":"2021-08-02T00:00:00Z","timestamp":1627862400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2022,10]]},"DOI":"10.1007\/s10208-021-09519-7","type":"journal-article","created":{"date-parts":[[2021,8,2]],"date-time":"2021-08-02T17:02:45Z","timestamp":1627923765000},"page":"1395-1462","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Vandermonde Varieties, Mirrored Spaces, and the Cohomology of Symmetric Semi-algebraic Sets"],"prefix":"10.1007","volume":"22","author":[{"given":"Saugata","family":"Basu","sequence":"first","affiliation":[]},{"given":"Cordian","family":"Riener","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,8,2]]},"reference":[{"issue":"2","key":"9519_CR1","first-page":"52","volume":"20","author":"VI Arnold","year":"1986","unstructured":"V.\u00a0I. Arnold, Hyperbolic polynomials and Vandermonde mappings, Funktsional. Anal. i Prilozhen. 20 (1986), no.\u00a02, 52\u201353.","journal-title":"Funktsional. Anal. i Prilozhen."},{"issue":"1","key":"9519_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/PL00009443","volume":"22","author":"S Basu","year":"1999","unstructured":"S.\u00a0Basu, On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets, Discret. Comput. Geom. 22 (1999), no.\u00a01, 1\u201318.","journal-title":"Discret. Comput. Geom."},{"issue":"10","key":"9519_CR3","doi-asserted-by":"publisher","first-page":"1125","DOI":"10.1016\/j.jsc.2006.07.001","volume":"41","author":"S Basu","year":"2006","unstructured":"S.\u00a0Basu, Computing the first few Betti numbers of semi-algebraic sets in single exponential time, J. Symb. Comput. 41 (2006), no.\u00a010, 1125\u20131154.","journal-title":"J. Symb. Comput."},{"issue":"1","key":"9519_CR4","doi-asserted-by":"publisher","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 (2008), no.\u00a01, 45\u201380.","journal-title":"Found. Comput. Math."},{"key":"9519_CR5","unstructured":"S.\u00a0Basu, Algorithms in real algebraic geometry: a survey, Real algebraic geometry, Panor. Synth\u00e8ses, vol.\u00a051, Soc. Math. France, Paris, 2017, pp.\u00a0107\u2013153."},{"issue":"1","key":"9519_CR6","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s13398-012-0076-4","volume":"107","author":"S Basu","year":"2013","unstructured":"S.\u00a0Basu, A.\u00a0Gabrielov, and N.\u00a0Vorobjov, Monotone functions and maps, Rev. R. Acad. Cienc. Exactas F\u00eds. Nat. Ser. A Mat. RACSAM 107 (2013), no.\u00a01, 5\u201333.","journal-title":"Rev. R. Acad. Cienc. Exactas F\u00eds. Nat. Ser. A Mat. RACSAM"},{"issue":"1","key":"9519_CR7","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1090\/S0894-0347-99-00311-2","volume":"13","author":"S Basu","year":"2000","unstructured":"S.\u00a0Basu, R.\u00a0Pollack, and M.-F. Roy, Computing roadmaps of semi-algebraic sets on a variety, J. Am. Math. Soc. 13 (2000), no.\u00a01, 55\u201382.","journal-title":"J. Am. Math. Soc."},{"issue":"1","key":"9519_CR8","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/s00037-005-0190-1","volume":"14","author":"S Basu","year":"2005","unstructured":"S.\u00a0Basu, R.\u00a0Pollack, and M.-F. Roy, Computing the Euler\u2013Poincar\u00e9 characteristics of sign conditions, Comput. Complex. 14 (2005), no.\u00a01, 53\u201371.","journal-title":"Comput. Complex."},{"key":"9519_CR9","doi-asserted-by":"crossref","unstructured":"S.\u00a0Basu, R.\u00a0Pollack, and M.-F. Roy, Algorithms in real algebraic geometry, Algorithms and Computation in Mathematics, vol.\u00a010, Springer-Verlag, Berlin, 2006 (second edition).","DOI":"10.1007\/3-540-33099-2"},{"issue":"1","key":"9519_CR10","doi-asserted-by":"publisher","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 (2008), no.\u00a01, 97\u2013136.","journal-title":"Found. Comput. Math."},{"key":"9519_CR11","doi-asserted-by":"crossref","unstructured":"S.\u00a0Basu and C.\u00a0Riener, Efficient algorithms for computing the Euler\u2013Poincar\u00e9 characteristic of symmetric semi-algebraic sets, Ordered algebraic structures and related topics, Contemp. Math., vol. 697, Am. Math. Soc., Providence, RI, 2017, pp.\u00a051\u201379.","DOI":"10.1090\/conm\/697\/14046"},{"issue":"4","key":"9519_CR12","doi-asserted-by":"publisher","first-page":"3241","DOI":"10.1007\/s00029-018-0401-7","volume":"24","author":"S Basu","year":"2018","unstructured":"S.\u00a0Basu and C.\u00a0Riener, On the equivariant Betti numbers of symmetric definable sets: vanishing, bounds and algorithms, Selecta Math. (N.S.) 24 (2018), no.\u00a04, 3241\u20133281.","journal-title":"Selecta Math. (N.S.)"},{"key":"9519_CR13","doi-asserted-by":"crossref","unstructured":"S.\u00a0Basu and C.\u00a0Riener, On the isotypic decomposition of cohomology modules of symmetric semi-algebraic sets: polynomial bounds on multiplicities, International Mathematics Research Notices (2018), rny062.","DOI":"10.1093\/imrn\/rny062"},{"issue":"2","key":"9519_CR14","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/s00454-014-9610-9","volume":"52","author":"S Basu","year":"2014","unstructured":"S.\u00a0Basu and M.-F. Roy, Divide and conquer roadmap for algebraic sets, Discret. Comput. Geom. 52 (2014), no.\u00a02, 278\u2013343.","journal-title":"Discret. Comput. Geom."},{"issue":"4","key":"9519_CR15","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/s10208-010-9062-4","volume":"10","author":"S Basu","year":"2010","unstructured":"S.\u00a0Basu and T.\u00a0Zell, Polynomial hierarchy, Betti numbers, and a real analogue of Toda\u2019s theorem, Found. Comput. Math. 10 (2010), no.\u00a04, 429\u2013454.","journal-title":"Found. Comput. Math."},{"key":"9519_CR16","doi-asserted-by":"crossref","unstructured":"L.\u00a0Blum, F.\u00a0Cucker, M.\u00a0Shub, and S.\u00a0Smale, Complexity and real computation, Springer-Verlag, New York, 1998, With a foreword by Richard M. Karp.","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"9519_CR17","unstructured":"J.\u00a0Bochnak, M.\u00a0Coste, and M.-F. Roy, G\u00e9om\u00e9trie alg\u00e9brique r\u00e9elle (second edition in english: Real algebraic geometry), Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas ], vol. 12 (36), Springer-Verlag, Berlin, 1987 (1998)."},{"issue":"1","key":"9519_CR18","doi-asserted-by":"publisher","first-page":"37","DOI":"10.4064\/-44-1-37-50","volume":"44","author":"L Br\u00f6cker","year":"1998","unstructured":"L.\u00a0Br\u00f6cker, On symmetric semialgebraic sets and orbit spaces, Banach Center Publ. 44 (1998), no.\u00a01, 37\u201350.","journal-title":"Banach Center Publ."},{"key":"9519_CR19","unstructured":"P.\u00a0B\u00fcrgisser and F.\u00a0Cucker, Variations by complexity theorists on three themes of Euler, B\u00e9zout, Betti, and Poincar\u00e9, Complexity of computations and proofs, Quad. Mat., vol.\u00a013, Dept. Math., Seconda Univ. Napoli, Caserta, 2004, pp.\u00a073\u2013151."},{"key":"9519_CR20","doi-asserted-by":"crossref","unstructured":"P.\u00a0B\u00fcrgisser, F.\u00a0Cucker, and P.\u00a0Lairez, Computing the homology of basic semialgebraic sets in weak exponential time, J. ACM 66 (2018), no.\u00a01, 5:1\u20135:30.","DOI":"10.1145\/3275242"},{"key":"9519_CR21","doi-asserted-by":"crossref","unstructured":"P.\u00a0B\u00fcrgisser, F.\u00a0Cucker, and P.\u00a0Lairez, Computing the homology of basic semialgebraic sets in weak exponential time, J. ACM 66 (2019), no.\u00a01, Art. 5, 30, [Publication date initially given as 2018].","DOI":"10.1145\/3275242"},{"key":"9519_CR22","doi-asserted-by":"crossref","unstructured":"P.\u00a0B\u00fcrgisser, F.\u00a0Cucker, and J.\u00a0Tonelli-Cueto, Computing the Homology of Semialgebraic Sets. II: General formulas, arXiv e-prints (2019), arXiv:1903.10710.","DOI":"10.1007\/s10208-019-09418-y"},{"issue":"1","key":"9519_CR23","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s10208-019-09418-y","volume":"20","author":"P B\u00fcrgisser","year":"2020","unstructured":"P.\u00a0B\u00fcrgisser, F.\u00a0Cucker, and J.\u00a0Tonelli-Cueto, Computing the homology of semialgebraic sets. I: Lax formulas, Found. Comput. Math. 20 (2020), no.\u00a01, 71\u2013118.","journal-title":"Found. Comput. Math."},{"key":"9519_CR24","volume-title":"The complexity of robot motion planning","author":"J Canny","year":"1987","unstructured":"J.\u00a0Canny, The complexity of robot motion planning, MIT Press, Cambridge, 1987."},{"key":"9519_CR25","doi-asserted-by":"crossref","unstructured":"T.\u00a0Ceccherini-Silberstein, F.\u00a0Scarabotti, and F.\u00a0Tolli, Representation theory of the symmetric groups, Cambridge Studies in Advanced Mathematics, vol. 121, Cambridge University Press, Cambridge, 2010, The Okounkov\u2013Vershik approach, character formulas, and partition algebras.","DOI":"10.1017\/CBO9781139192361"},{"issue":"2","key":"9519_CR26","doi-asserted-by":"publisher","first-page":"293","DOI":"10.2307\/2007079","volume":"117","author":"MW Davis","year":"1983","unstructured":"M.\u00a0W. Davis, Groups generated by reflections and aspherical manifolds not covered by Euclidean space, Ann. Math. 117 (1983), no.\u00a02, 293\u2013324.","journal-title":"Ann. Math."},{"key":"9519_CR27","volume-title":"The geometry and topology of Coxeter groups, London Mathematical Society Monographs Series","author":"MW Davis","year":"2008","unstructured":"M.\u00a0W. Davis, The geometry and topology of Coxeter groups, London Mathematical Society Monographs Series, vol.\u00a032, Princeton University Press, Princeton, 2008."},{"key":"9519_CR28","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1215\/S0012-7094-41-00826-8","volume":"8","author":"P Erd\u0151s","year":"1941","unstructured":"P.\u00a0Erd\u0151s and J.\u00a0Lehner, The distribution of the number of summands in the partitions of a positive integer, Duke Math. J. 8 (1941), 335\u2013345.","journal-title":"Duke Math. J."},{"issue":"1","key":"9519_CR29","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1112\/jlms\/jdp006","volume":"80","author":"A Gabrielov","year":"2009","unstructured":"A.\u00a0Gabrielov and N.\u00a0Vorobjov, Approximation of definable sets by compact families, and upper bounds on homotopy and homology, J. Lond. Math. Soc. 80 (2009), no.\u00a01, 35\u201354.","journal-title":"J. Lond. Math. Soc."},{"issue":"2","key":"9519_CR30","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1070\/RM1987v042n02ABEH001314","volume":"42","author":"A Givental","year":"1987","unstructured":"A.\u00a0Givental, Moments of random variables and the equivariant Morse lemma, Rus. Math. Surv. 42 (1987), no.\u00a02, 275\u2013276.","journal-title":"Rus. Math. Surv."},{"key":"9519_CR31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-82783-9","volume-title":"Cohomology of sheaves","author":"B Iversen","year":"1986","unstructured":"B.\u00a0Iversen, Cohomology of sheaves, Universitext, Springer-Verlag, Berlin, 1986."},{"issue":"3\u20134","key":"9519_CR32","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1017\/S0308210500018679","volume":"112","author":"VP Kostov","year":"1989","unstructured":"V.P. Kostov, On the geometric properties of Vandermonde\u2019s mapping and on the problem of moments, Proc. Royal Soc. Edinb.: Sect. A Math. 112 (1989), no.\u00a03-4, 203\u2013211.","journal-title":"Proc. Royal Soc. Edinb.: Sect. A Math."},{"key":"9519_CR33","unstructured":"J.-L. Koszul, Lectures on groups of transformations, Notes by R. R. Simha and R. Sridharan. Tata Institute of Fundamental Research Lectures on Mathematics, No. 32, Tata Institute of Fundamental Research, Bombay, 1965."},{"key":"9519_CR34","volume-title":"Combinatory analysis, two volumes (bound as one)","author":"PA MacMahon","year":"1960","unstructured":"P.\u00a0A. MacMahon, Combinatory analysis, two volumes (bound as one), Chelsea Publishing Co., New York, 1960."},{"key":"9519_CR35","unstructured":"L.\u00a0Manivel, Symmetric functions, Schubert polynomials and degeneracy loci, SMF\/AMS Texts and Monographs, vol.\u00a06, American Mathematical Society, Providence, RI; Soci\u00e9t\u00e9 Math\u00e9matique de France, Paris, 2001, Translated from the 1998 French original by John R. Swallow, Cours Sp\u00e9cialis\u00e9s [Specialized Courses], 3."},{"issue":"3","key":"9519_CR36","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/BF02571438","volume":"211","author":"I Meguerditchian","year":"1992","unstructured":"I.\u00a0Meguerditchian, A theorem on the escape from the space of hyperbolic polynomials, Math. Z. 211 (1992), no.\u00a03, 449\u2013460.","journal-title":"Math. Z."},{"key":"9519_CR37","unstructured":"C.\u00a0Procesi, Lie groups, Universitext, Springer, New York, 2007, An approach through invariants and representations."},{"issue":"3","key":"9519_CR38","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/BF01388587","volume":"81","author":"C Procesi","year":"1985","unstructured":"C.\u00a0Procesi and G.\u00a0Schwarz, Inequalities defining orbit spaces, Invent. Math. 81 (1985), no.\u00a03, 539\u2013554.","journal-title":"Invent. Math."},{"key":"9519_CR39","doi-asserted-by":"crossref","unstructured":"J.\u00a0H. Reif, Complexity of the mover\u2019s problem and generalizations, Proceedings of the 20th Annual Symposium on Foundations of Computer Science (Washington, DC, USA), SFCS \u201979, IEEE Computer Society, 1979, pp.\u00a0421\u2013427.","DOI":"10.1109\/SFCS.1979.10"},{"issue":"4","key":"9519_CR40","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1016\/j.jpaa.2011.08.012","volume":"216","author":"C Riener","year":"2012","unstructured":"C.\u00a0Riener, On the degree and half-degree principle for symmetric polynomials, J. Pure Appl. Algebra 216 (2012), no.\u00a04, 850\u2013856.","journal-title":"J. Pure Appl. Algebra"},{"key":"9519_CR41","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1016\/0196-8858(83)90014-3","volume":"4","author":"J Schwartz","year":"1983","unstructured":"J.\u00a0Schwartz and M.\u00a0Sharir, On the piano movers\u2019 problem ii. General techniques for computing topological properties of real algebraic manifolds, Adv. Appl. Math. 4 (1983), 298\u2013351.","journal-title":"Adv. Appl. Math."},{"key":"9519_CR42","doi-asserted-by":"crossref","unstructured":"J.-P. Serre, Linear representations of finite groups, Springer-Verlag, New York-Heidelberg, 1977, Translated from the second French edition by Leonard L. Scott, Graduate Texts in Mathematics, Vol. 42.","DOI":"10.1007\/978-1-4684-9458-7"},{"key":"9519_CR43","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/0021-8693(68)90022-7","volume":"9","author":"L Solomon","year":"1968","unstructured":"L.\u00a0Solomon, A decomposition of the group algebra of a finite Coxeter group, J. Algebra 9 (1968), 220\u2013239.","journal-title":"J. Algebra"},{"key":"9519_CR44","volume-title":"Algebraic topology","author":"EH Spanier","year":"1966","unstructured":"E.\u00a0H. Spanier, Algebraic topology, McGraw-Hill Book Co., New York, 1966."},{"issue":"1","key":"9519_CR45","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/S0022-247X(03)00301-9","volume":"284","author":"V Timofte","year":"2003","unstructured":"V.\u00a0Timofte, On the positivity of symmetric polynomial functions. I. General results, J. Math. Anal. Appl. 284 (2003), no.\u00a01, 174\u2013190.","journal-title":"J. Math. Anal. Appl."},{"key":"9519_CR46","unstructured":"J.\u00a0Tits, On buildings and their applications, Proceedings of the International Congress of Mathematicians (Vancouver, B. C., 1974), Vol. 1 (1975), 209\u2013220."},{"key":"9519_CR47","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511525919","volume-title":"Tame topology and o-minimal structures, London Mathematical Society Lecture Note Series","author":"L van den Dries","year":"1998","unstructured":"L.\u00a0van\u00a0den Dries, Tame topology and o-minimal structures, London Mathematical Society Lecture Note Series, vol. 248, Cambridge University Press, Cambridge, 1998."},{"key":"9519_CR48","first-page":"1072","volume":"35","author":"\u00c8B Vinberg","year":"1971","unstructured":"\u00c8.\u00a0B. Vinberg, Discrete linear groups that are generated by reflections, Izv. Akad. Nauk SSSR Ser. Mat. 35 (1971), 1072\u20131112.","journal-title":"Izv. Akad. Nauk SSSR Ser. Mat."}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-021-09519-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10208-021-09519-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-021-09519-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,18]],"date-time":"2022-10-18T20:34:49Z","timestamp":1666125289000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10208-021-09519-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,2]]},"references-count":48,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["9519"],"URL":"https:\/\/doi.org\/10.1007\/s10208-021-09519-7","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,2]]},"assertion":[{"value":"1 June 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 April 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 April 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 August 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}