{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T13:50:21Z","timestamp":1762782621539,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":42,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,7,18]],"date-time":"2021-07-18T00:00:00Z","timestamp":1626566400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-18-CE33-0011, ANR-19-CE40-0018, ANR-FWF ANR-19-CE48-0015"],"award-info":[{"award-number":["ANR-18-CE33-0011, ANR-19-CE40-0018, ANR-FWF ANR-19-CE48-0015"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010665","name":"H2020 Marie Sk\u0142odowska-Curie Actions","doi-asserted-by":"publisher","award":["813211 (POEMA)"],"award-info":[{"award-number":["813211 (POEMA)"]}],"id":[{"id":"10.13039\/100010665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,7,18]]},"DOI":"10.1145\/3452143.3465546","type":"proceedings-article","created":{"date-parts":[[2021,7,13]],"date-time":"2021-07-13T22:32:21Z","timestamp":1626215541000},"page":"265-272","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Faster One Block Quantifier Elimination for Regular Polynomial Systems of Equations"],"prefix":"10.1145","author":[{"given":"Huu Phuoc","family":"Le","sequence":"first","affiliation":[{"name":"Sorbonne Universit\u00e9, CNRS, Paris, France"}]},{"given":"Mohab","family":"Safey El Din","sequence":"additional","affiliation":[{"name":"Sorbonne Universit\u00e9, CNRS, Paris, France"}]}],"member":"320","published-online":{"date-parts":[[2021,7,18]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_1_1_1","DOI":"10.1007\/3-540-45351-2_9"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_2_1","DOI":"10.1016\/j.jsc.2014.09.025"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_3_1","DOI":"10.1145\/235809.235813"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_4_1","DOI":"10.1007\/3-540-33099-2"},{"key":"e_1_3_2_1_5_1","volume-title":"Preprint","author":"Berthomieu J.","year":"2021","unstructured":"Berthomieu, J., Eder, C., and Safey El Din, M. msolve: A Library for Solving Polynomial Systems. Preprint, Feb. 2021."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_6_1","DOI":"10.1006\/jsco.2001.0463"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_7_1","DOI":"10.1007\/11870814_7"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_8_1","DOI":"10.1145\/1093390.1093393"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_9_1","DOI":"10.1016\/S0747-7171(08)80152-6"},{"key":"e_1_3_2_1_10_1","volume-title":"An Introduction to Computational Algebraic Geometry and Commutative Algebra, (Undergraduate Texts in Mathematics)","author":"Cox D. A.","year":"2007","unstructured":"Cox, D. A., Little, J., and O'Shea, D. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, (Undergraduate Texts in Mathematics). Springer-Verlag, Berlin, Heidelberg, 2007."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_11_1","DOI":"10.1016\/S0747-7171(88)80004-X"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_12_1","DOI":"10.1023\/A:1006031329384"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_13_1","DOI":"10.1007\/978-3-540-30210-0_8"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_14_1","DOI":"10.1007\/978-1-4612-5350-1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_15_1","DOI":"10.1007\/978-3-642-15582-6_17"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_16_1","DOI":"10.1016\/j.jsc.2013.03.004"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_17_1","DOI":"10.1016\/S0747-7171(88)80006-3"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_18_1","DOI":"10.1515\/crll.1856.52.39"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_19_1","DOI":"10.1145\/96877.96943"},{"key":"e_1_3_2_1_20_1","first-page":"183","volume-title":"Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation (New York, NY, USA, 2009), ISSAC '09, Association for Computing Machinery","author":"Hong H.","unstructured":"Hong, H., and Safey El Din, M. Variant real quantifier elimination: Algorithm and application. In Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation (New York, NY, USA, 2009), ISSAC '09, Association for Computing Machinery, p. 183--190."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_21_1","DOI":"10.1016\/j.jsc.2011.05.014"},{"key":"e_1_3_2_1_22_1","volume-title":"Preprint","author":"Le H. P.","year":"2020","unstructured":"Le, H. P., and Safey El Din, M. Solving parametric systems of polynomial equations over the reals through Hermite matrices. Preprint, Nov. 2020."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_23_1","DOI":"10.1093\/comjnl\/36.5.497"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_24_1","DOI":"10.1016\/S0747-7171(88)80010-5"},{"key":"e_1_3_2_1_25_1","first-page":"145","volume-title":"Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation (New York, NY, USA, 1999), ISSAC '99, Association for Computing Machinery","author":"McCallum S.","unstructured":"McCallum, S. On projection in CAD-based quantifier elimination with equational constraint. In Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation (New York, NY, USA, 1999), ISSAC '99, Association for Computing Machinery, p. 145--149."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_26_1","DOI":"10.1137\/080716670"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_27_1","DOI":"10.1007\/978-1-4612-2752-6_15"},{"key":"e_1_3_2_1_28_1","first-page":"3","article-title":"On the computational complexity and geometry of the first-order theory of the reals. Part III: Quantifier elimination","volume":"13","author":"Renegar J","year":"1992","unstructured":"Renegar, J. On the computational complexity and geometry of the first-order theory of the reals. Part III: Quantifier elimination. J. Symb. Comput. 13, 3 (Mar. 1992), 329--352.","journal-title":"J. Symb. Comput."},{"key":"e_1_3_2_1_29_1","volume-title":"RAGlib (version 3.4)","author":"Safey El Din M.","year":"2017","unstructured":"Safey El Din, M. Real alebraic geometry library, RAGlib (version 3.4), 2017."},{"key":"e_1_3_2_1_30_1","first-page":"224","volume-title":"Proc. of the 2003 Int. Symp. on Symb. and Alg. Comp. (NY, USA, 2003), ISSAC '03, ACM","author":"Safey El Din M.","unstructured":"Safey El Din, M., and Schost, E. Polar varieties and computation of one point in each connected component of a smooth real algebraic set. In Proc. of the 2003 Int. Symp. on Symb. and Alg. Comp. (NY, USA, 2003), ISSAC '03, ACM, p. 224--231."},{"key":"e_1_3_2_1_31_1","first-page":"6","article-title":"A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets","volume":"63","author":"Safey El Din M.","year":"2017","unstructured":"Safey El Din, M., and Schost, \u00c9. A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets. J. ACM 63, 6 (Jan. 2017), 48:1--48:37.","journal-title":"J. ACM"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_32_1","DOI":"10.2307\/1969640"},{"key":"e_1_3_2_1_33_1","first-page":"240","volume-title":"Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation (New York, NY, USA, 2003), ISSAC '03, Association for Computing Machinery","author":"Seidl A.","unstructured":"Seidl, A., and Sturm, T. A generic projection operator for partial cylindrical algebraic decomposition. In Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation (New York, NY, USA, 2003), ISSAC '03, Association for Computing Machinery, p. 240--247."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_34_1","DOI":"10.1007\/978-3-642-37956-7"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_35_1","DOI":"10.1137\/130936294"},{"key":"e_1_3_2_1_36_1","first-page":"9","article-title":"Decomposition using validated numerics","volume":"41","author":"Cylindrical Algebraic","year":"2006","unstructured":"A. W. Cylindrical Algebraic Decomposition using validated numerics. J. Symb. Comput 41, 9 (2006), 1021--1038.","journal-title":"J. Symb. Comput"},{"key":"e_1_3_2_1_37_1","first-page":"329","volume-title":"Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation (New York, NY, USA, 2011), ISSAC '11, Association for Computing Machinery","author":"Sturm T.","unstructured":"Sturm, T., and Tiwari, A. Verification and synthesis using real quantifier elimination. In Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation (New York, NY, USA, 2011), ISSAC '11, Association for Computing Machinery, p. 329--336."},{"key":"e_1_3_2_1_38_1","first-page":"58","volume-title":"Heidelberg","author":"Sturm T.","year":"1996","unstructured":"Sturm, T., and Weispfenning, V. Computational geometry problems in REDLOG. In Selected Papers from the International Workshop on Automated Deduction in Geometry (Berlin, Heidelberg, 1996), Springer-Verlag, p. 58--86."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_39_1","DOI":"10.1525\/9780520348097"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_40_1","DOI":"10.1016\/S0747-7171(88)80003-8"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_41_1","DOI":"10.1016\/0747-7171(92)90023-W"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_42_1","DOI":"10.1007\/978-3-7091-9459-1_20"}],"event":{"sponsor":["SIGSAM ACM Special Interest Group on Symbolic and Algebraic Manipulation"],"acronym":"ISSAC '21","name":"ISSAC '21: International Symposium on Symbolic and Algebraic Computation","location":"Virtual Event Russian Federation"},"container-title":["Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3452143.3465546","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3452143.3465546","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:08Z","timestamp":1750193288000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3452143.3465546"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,18]]},"references-count":42,"alternative-id":["10.1145\/3452143.3465546","10.1145\/3452143"],"URL":"https:\/\/doi.org\/10.1145\/3452143.3465546","relation":{},"subject":[],"published":{"date-parts":[[2021,7,18]]},"assertion":[{"value":"2021-07-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}