{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T11:44:31Z","timestamp":1762775071867,"version":"build-2065373602"},"publisher-location":"New York, NY, USA","reference-count":56,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,7,28]]},"DOI":"10.1145\/3747199.3747572","type":"proceedings-article","created":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T10:51:17Z","timestamp":1762771877000},"page":"284-292","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Computing Polynomial Representation in Subrings of Multivariate Polynomial Rings"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2285-7801","authenticated-orcid":false,"given":"Thi Xuan","family":"Vu","sequence":"first","affiliation":[{"name":"Univ. Lille, CNRS, Centrale Lille, UMR 9189 CRIStAL, Lille, France"}]}],"member":"320","published-online":{"date-parts":[[2025,11,10]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"W. Baur and V. Strassen. 1983. The complexity of partial derivatives. Theoretical Computer Science 22 3 (1983) 317\u2013330.","key":"e_1_3_3_1_2_2","DOI":"10.1016\/0304-3975(83)90110-X"},{"doi-asserted-by":"crossref","unstructured":"M. Beecken J. Mittmann and N. Saxena. 2013. Algebraic independence and blackbox identity testing. Information and Computation 222 (2013) 2\u201319.","key":"e_1_3_3_1_3_2","DOI":"10.1016\/j.ic.2012.10.004"},{"doi-asserted-by":"crossref","unstructured":"S.\u00a0J. Berkowitz. 1984. On computing the determinant in small parallel time using a small number of processors. Information processing letters 18 3 (1984) 147\u2013150.","key":"e_1_3_3_1_4_2","DOI":"10.1016\/0020-0190(84)90018-8"},{"doi-asserted-by":"publisher","key":"e_1_3_3_1_5_2","DOI":"10.4230\/LIPIcs.ITCS.2019.47"},{"doi-asserted-by":"crossref","unstructured":"D.\u00a0G. Cantor and E. Kaltofen. 1991. On fast multiplication of polynomials over arbitrary algebras. Acta Informatica 28 7 (1991) 693\u2013701.","key":"e_1_3_3_1_6_2","DOI":"10.1007\/BF01178683"},{"doi-asserted-by":"crossref","unstructured":"L. Cardelli M. Tribastone M. Tschaikowski and A. Vandin. 2017. Maximal aggregation of polynomial dynamical systems. Proceedings of the National Academy of Sciences 114 38 (2017) 10029\u201310034.","key":"e_1_3_3_1_7_2","DOI":"10.1073\/pnas.1702697114"},{"doi-asserted-by":"crossref","unstructured":"P. Chaugule M. Kumar N. Limaye C.\u00a0K. Mohapatra A. She and S. Srinivasan. 2023. Schur polynomials do not have small formulas if the determinant does not. Computational Complexity 32 1 (2023) 3.","key":"e_1_3_3_1_8_2","DOI":"10.1007\/s00037-023-00236-x"},{"doi-asserted-by":"crossref","unstructured":"C. Chevalley. 1955. Invariants of finite groups generated by reflections. American Journal of Mathematics 77 4 (1955) 778\u2013782.","key":"e_1_3_3_1_9_2","DOI":"10.2307\/2372597"},{"doi-asserted-by":"publisher","unstructured":"A. Colin. 1997. Solving a system of algebraic equations with symmetries. Journal of Pure and Applied Algebra 117-118 (1997) 195 \u2013 215. 10.1016\/S0022-4049(97)00011-X","key":"e_1_3_3_1_10_2","DOI":"10.1016\/S0022-4049(97)00011-X"},{"doi-asserted-by":"publisher","key":"e_1_3_3_1_11_2","DOI":"10.1007\/978-0-387-35651-8"},{"doi-asserted-by":"crossref","unstructured":"X. Dahan \u00c9. Schost and J. Wu. 2009. Evaluation properties of invariant polynomials. Journal of Symbolic Computation 44 11 (2009) 1592\u20131604.","key":"e_1_3_3_1_12_2","DOI":"10.1016\/j.jsc.2008.12.002"},{"doi-asserted-by":"crossref","unstructured":"J. Damon. 1997. A global weighted version of B\u00e9zout\u2019s theorem. The Arnoldfest (Toronto ON 1997) 24 (1997) 115\u2013129.","key":"e_1_3_3_1_13_2","DOI":"10.1090\/fic\/024\/07"},{"unstructured":"A. Demin E. Demitraki and G. Pogudin. 2023. Exact linear reductions of dynamical models. arXiv preprint arXiv:https:\/\/arXiv.org\/abs\/2301.11653 (2023).","key":"e_1_3_3_1_14_2"},{"doi-asserted-by":"publisher","key":"e_1_3_3_1_15_2","DOI":"10.1007\/3-540-48405-1_20"},{"doi-asserted-by":"crossref","unstructured":"J-C. Faug\u00e8re G. Labahn M. Safey El\u00a0Din \u00c9. Schost and T.\u00a0X. Vu. 2023. Computing critical points for invariant algebraic systems. Journal of Symbolic Computation 116 (2023) 365\u2013399.","key":"e_1_3_3_1_16_2","DOI":"10.1016\/j.jsc.2022.10.002"},{"doi-asserted-by":"crossref","unstructured":"J.-C. Faug\u00e8re and L. Perret. 2009. An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography. Journal of Symbolic Computation 44 12 (2009) 1676\u20131689.","key":"e_1_3_3_1_17_2","DOI":"10.1016\/j.jsc.2008.02.005"},{"doi-asserted-by":"publisher","key":"e_1_3_3_1_18_2","DOI":"10.1007\/11818175_21"},{"doi-asserted-by":"publisher","unstructured":"J.-C. Faug\u00e8re M. Safey El\u00a0Din and T. Verron. 2016. On the complexity of computing Gr\u00f6bner bases for weighted homogeneous systems. Journal of Symbolic Computation 76 (2016) 107 \u2013 141. 10.1016\/j.jsc.2015.12.001","key":"e_1_3_3_1_19_2","DOI":"10.1016\/j.jsc.2015.12.001"},{"doi-asserted-by":"crossref","unstructured":"J. Feret V. Danos J. Krivine R. Harmer and W. Fontana. 2009. Internal coarse-graining of molecular systems. Proceedings of the National Academy of Sciences 106 16 (2009) 6453\u20136458.","key":"e_1_3_3_1_20_2","DOI":"10.1073\/pnas.0809908106"},{"doi-asserted-by":"crossref","unstructured":"K. Gatermann. 1996. Semi-invariants equivariants and algorithms. Applicable Algebra in Engineering Communication and Computing 7 2 (1996) 105\u2013124.","key":"e_1_3_3_1_21_2","DOI":"10.1007\/BF01191379"},{"doi-asserted-by":"crossref","unstructured":"P. Gaudry \u00c9. Schost and N.\u00a0M. Thi\u00e9ry. 2006. Evaluation properties of symmetric polynomials. International Journal of Algebra and Computation 16 03 (2006) 505\u2013523.","key":"e_1_3_3_1_22_2","DOI":"10.1142\/S0218196706003128"},{"doi-asserted-by":"crossref","unstructured":"J. Giusti M.and\u00a0Heintz J.\u00a0E. Morais J. Morgenstem and L.\u00a0M. Pardo. 1998. Straight-line programs in geometric elimination theory. Journal of pure and applied algebra 124 1-3 (1998) 101\u2013146.","key":"e_1_3_3_1_23_2","DOI":"10.1016\/S0022-4049(96)00099-0"},{"doi-asserted-by":"crossref","unstructured":"M. Giusti J. Heintz K. H\u00e4gele J.\u00a0E. Morais L.\u00a0M. Pardo and J.\u00a0L. Montana. 1997. Lower bounds for Diophantine approximations. Journal of Pure and Applied Algebra 117 (1997) 277\u2013317.","key":"e_1_3_3_1_24_2","DOI":"10.1016\/S0022-4049(97)00015-7"},{"doi-asserted-by":"publisher","key":"e_1_3_3_1_25_2","DOI":"10.1007\/3-540-60114-7_16"},{"doi-asserted-by":"crossref","unstructured":"M. Giusti G. Lecerf and B. Salvy. 2001. A Gr\u00f6bner free alternative for polynomial system solving. Journal of complexity 17 1 (2001) 154\u2013211.","key":"e_1_3_3_1_26_2","DOI":"10.1006\/jcom.2000.0571"},{"doi-asserted-by":"crossref","unstructured":"D. Harvey and J. van\u00a0der Hoeven. 2022. Polynomial multiplication over finite fields in time O(n\u2009log\u2009n). Journal of the ACM (JACM) 69 2 (2022) 1\u201340.","key":"e_1_3_3_1_27_2","DOI":"10.1145\/3505584"},{"doi-asserted-by":"crossref","unstructured":"J. Heintz T. Krick S. Puddu J. Sabia and A. Waissbein. 2000. Deformation techniques for efficient polynomial equation solving. Journal of Complexity 16 1 (2000) 70\u2013109.","key":"e_1_3_3_1_28_2","DOI":"10.1006\/jcom.1999.0529"},{"doi-asserted-by":"publisher","key":"e_1_3_3_1_29_2","DOI":"10.1007\/3-540-10843-2_2"},{"doi-asserted-by":"crossref","unstructured":"E. Hubert and G. Labahn. 2013. Scaling invariants and symmetry reduction of dynamical systems. Foundations of Computational Mathematics 13 (2013) 479\u2013516.","key":"e_1_3_3_1_30_2","DOI":"10.1007\/s10208-013-9165-9"},{"key":"e_1_3_3_1_31_2","series-title":"Cambridge Studies in Advanced Mathematics","volume-title":"Reflection Groups and Coxeter Groups","author":"Humphreys J.\u00a0E.","year":"1992","unstructured":"J.\u00a0E. Humphreys. 1992. Reflection Groups and Coxeter Groups. Cambridge Studies in Advanced Mathematics, Vol.\u00a029. Cambridge University Press, Cambridge, UK."},{"doi-asserted-by":"crossref","unstructured":"A. Jim\u00e9nez-Pastor and G. Pogudin. 2022. Computing exact nonlinear reductions of dynamical models. ACM Communications in Computer Algebra 56 2 (2022) 25\u201331.","key":"e_1_3_3_1_32_2","DOI":"10.1145\/3572867.3572869"},{"doi-asserted-by":"crossref","unstructured":"E. Kaltofen. 1988. Greatest common divisors of polynomials given by straight-line programs. Journal of the ACM (JACM) 35 1 (1988) 231\u2013264.","key":"e_1_3_3_1_33_2","DOI":"10.1145\/42267.45069"},{"unstructured":"E. Kaltofen. 1989. Factorization of polynomials given by straight-line programs. Adv. Comput. Res. 5 (1989) 375\u2013412.","key":"e_1_3_3_1_34_2"},{"doi-asserted-by":"publisher","key":"e_1_3_3_1_35_2","DOI":"10.5555\/246346.246374"},{"doi-asserted-by":"crossref","unstructured":"L. Kronecker. 1882. Grundz\u00fcge einer arithmetischen Theorie der algebraischen Gr\u00f6ssen. Journal f\u00fcr die Reine und Angewandte Mathematik 92 (1882) 1\u2013122.","key":"e_1_3_3_1_36_2","DOI":"10.1515\/crll.1882.92.1"},{"doi-asserted-by":"publisher","key":"e_1_3_3_1_37_2","DOI":"10.1145\/3597066.3597097"},{"doi-asserted-by":"crossref","unstructured":"G. Labahn M. Safey El\u00a0Din \u00c9. Schost and T.\u00a0X. Vu. 2021. Homotopy techniques for solving sparse column support determinantal polynomial systems. Journal of Complexity 66 (2021) 101557.","key":"e_1_3_3_1_38_2","DOI":"10.1016\/j.jco.2021.101557"},{"unstructured":"U.\u00a0J.\u00a0J. Le\u00a0Verrier. 1840. Sur les variations s\u00e9culaires des \u00e9l\u00e9ments elliptiques des sept plan\u00e8tes principales: Mercure V\u00e9nus La Terre Mars Jupiter Saturne et Uranus. J. Math. Pures Appli 4 1840 (1840) 220\u2013254.","key":"e_1_3_3_1_39_2"},{"doi-asserted-by":"crossref","unstructured":"G. Lecerf. 2003. Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers. Journal of Complexity 19 4 (2003) 564\u2013596.","key":"e_1_3_3_1_40_2","DOI":"10.1016\/S0885-064X(03)00031-1"},{"unstructured":"G. Lecerf and \u00c9. Schost. 2003. Fast multivariate power series multiplication in characteristic zero. Electronic Journal of SADIO (EJS) 5 (2003) 1\u201310.","key":"e_1_3_3_1_41_2"},{"doi-asserted-by":"crossref","unstructured":"A. Ovchinnikov I. P\u00e9rez\u00a0Verona G. Pogudin and M. Tribastone. 2021. CLUE: exact maximal reduction of kinetic models by constrained lumping of differential equations. Bioinformatics 37 12 (2021) 1732\u20131738.","key":"e_1_3_3_1_42_2","DOI":"10.1093\/bioinformatics\/btab010"},{"doi-asserted-by":"publisher","key":"e_1_3_3_1_43_2","DOI":"10.1007\/BFb0028492"},{"doi-asserted-by":"publisher","key":"e_1_3_3_1_44_2","DOI":"10.1145\/3666000.3669687"},{"doi-asserted-by":"crossref","unstructured":"M. Safey El\u00a0Din and \u00c9. Schost. 2017. A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets. Journal of the ACM (JACM) 63 6 (2017) 1\u201337.","key":"e_1_3_3_1_45_2","DOI":"10.1145\/2996450"},{"doi-asserted-by":"crossref","unstructured":"A. Sch\u00f6nhage. 1977. Schnelle Multiplikation von polynomen \u00fcber K\u00f6rpern der Charakteristik 2. Acta Informatica 7 4 (1977) 395\u2013398.","key":"e_1_3_3_1_46_2","DOI":"10.1007\/BF00289470"},{"doi-asserted-by":"crossref","unstructured":"A. Sch\u00f6nhage and V. Strassen. 1971. Schnelle Multiplikation gro\u00dfer Zahlen. Computing 7 3 (1971) 281\u2013292.","key":"e_1_3_3_1_47_2","DOI":"10.1007\/BF02242355"},{"doi-asserted-by":"crossref","unstructured":"\u00c9. Schost. 2003. Computing parametric geometric resolutions. Applicable Algebra in Engineering Communication and Computing 13 5 (2003) 349\u2013393.","key":"e_1_3_3_1_48_2","DOI":"10.1007\/s00200-002-0109-x"},{"doi-asserted-by":"crossref","unstructured":"J.\u00a0T. Schwartz. 1980. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM (JACM) 27 4 (1980) 701\u2013717.","key":"e_1_3_3_1_49_2","DOI":"10.1145\/322217.322225"},{"unstructured":"J.-P. Serre. 1965. Alg\u00e8bre Locale - Multiplicit\u00e9s volume 11 of Lectures notes in mathematics.","key":"e_1_3_3_1_50_2"},{"doi-asserted-by":"crossref","unstructured":"G.\u00a0C Shephard and J.\u00a0A. Todd. 1954. Finite unitary reflection groups. Canadian Journal of Mathematics 6 (1954) 274\u2013304.","key":"e_1_3_3_1_51_2","DOI":"10.4153\/CJM-1954-028-3"},{"doi-asserted-by":"publisher","key":"e_1_3_3_1_52_2","DOI":"10.1007\/3-540-56686-4_34"},{"key":"e_1_3_3_1_53_2","volume-title":"Modern Computer Algebra (2 ed.)","author":"Gathen J. von\u00a0zur","year":"2003","unstructured":"J. von\u00a0zur Gathen and J. Gerhard. 2003. Modern Computer Algebra (2 ed.). Cambridge University Press, New York, NY, USA."},{"doi-asserted-by":"crossref","unstructured":"J. von\u00a0zur Gathen J. Gutierrez and R. Rubio. 2003. Multivariate polynomial decomposition. Applicable Algebra in Engineering Communication and Computing 14 1 (2003) 11\u201331.","key":"e_1_3_3_1_54_2","DOI":"10.1007\/s00200-003-0122-8"},{"doi-asserted-by":"publisher","key":"e_1_3_3_1_55_2","DOI":"10.1145\/3476446.3536181"},{"doi-asserted-by":"crossref","unstructured":"P.\u00a0A. Worfolk. 1994. Zeros of equivariant vector fields: Algorithms for an invariant approach. Journal of Symbolic Computation 17 6 (1994) 487\u2013511.","key":"e_1_3_3_1_56_2","DOI":"10.1006\/jsco.1994.1031"},{"doi-asserted-by":"crossref","unstructured":"D. Ye Z. Dai and K.-Y. Lam. 2001. Decomposing attacks on asymmetric cryptography based on mapping compositions. Journal of Cryptology 14 (2001) 137\u2013150.","key":"e_1_3_3_1_57_2","DOI":"10.1007\/s00145-001-0001-z"}],"event":{"sponsor":["SIGSAM ACM Special Interest Group on Symbolic and Algebraic Manipulation"],"acronym":"ISSAC '25","name":"ISSAC '25: International Symposium on Symbolic and Algebraic Computation","location":"Guanajuato Mexico"},"container-title":["Proceedings of the 2025 International Symposium on Symbolic and Algebraic Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3747199.3747572","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T11:40:21Z","timestamp":1762774821000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3747199.3747572"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,28]]},"references-count":56,"alternative-id":["10.1145\/3747199.3747572","10.1145\/3747199"],"URL":"https:\/\/doi.org\/10.1145\/3747199.3747572","relation":{},"subject":[],"published":{"date-parts":[[2025,7,28]]},"assertion":[{"value":"2025-11-10","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}