{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T11:44:25Z","timestamp":1762775065393,"version":"build-2065373602"},"publisher-location":"New York, NY, USA","reference-count":31,"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.3747578","type":"proceedings-article","created":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T10:51:17Z","timestamp":1762771877000},"page":"337-344","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Computational Complexity of Polynomial Subalgebras"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4749-4920","authenticated-orcid":false,"given":"Elisabeth Leonie","family":"Kayser","sequence":"first","affiliation":[{"name":"Nonlinear Algebra Group, Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany"}]}],"member":"320","published-online":{"date-parts":[[2025,11,10]]},"reference":[{"key":"e_1_3_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"e_1_3_3_1_3_2","doi-asserted-by":"publisher","unstructured":"David Bayer and Michael Stillman. 1988. On the complexity of computing syzygies. Journal of Symbolic Computation 6 2 (1988) 135\u2013147. 10.1016\/S0747-7171(88)80039-7","DOI":"10.1016\/S0747-7171(88)80039-7"},{"key":"e_1_3_3_1_4_2","doi-asserted-by":"publisher","unstructured":"Barbara Betti Marta Panizzut and Simon Telen. 2025. Solving equations using Khovanskii bases. Journal of Symbolic Computation 126 (2025) 102340. 10.1016\/j.jsc.2024.102340","DOI":"10.1016\/j.jsc.2024.102340"},{"key":"e_1_3_3_1_5_2","doi-asserted-by":"publisher","unstructured":"A. Borodin S. Cook and N. Pippenger. 1983. Parallel computation for well-endowed rings and space-bounded probabilistic machines. Information and Control 58 1 (1983) 113\u2013136. 10.1016\/S0019-9958(83)80060-6","DOI":"10.1016\/S0019-9958(83)80060-6"},{"key":"e_1_3_3_1_6_2","doi-asserted-by":"publisher","unstructured":"Bruno Buchberger. 2006. Bruno Buchberger\u2019s PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. Journal of Symbolic Computation 41 3 (2006) 475\u2013511. 10.1016\/j.jsc.2005.09.007","DOI":"10.1016\/j.jsc.2005.09.007"},{"key":"e_1_3_3_1_7_2","doi-asserted-by":"publisher","unstructured":"Michael Burr Oliver Clarke Timothy Duff Jackson Leaman Nathan Nichols and Elise Walker. 2024. SubalgebraBases in Macaulay2. Journal of Software for Algebra and Geometry 14 1 (May 2024) 97\u2013109. 10.2140\/jsag.2024.14.97","DOI":"10.2140\/jsag.2024.14.97"},{"key":"e_1_3_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-41154-43"},{"key":"e_1_3_3_1_9_2","doi-asserted-by":"publisher","unstructured":"Alicia Dickenstein Noa\u00ef Fitchas Marc Giusti and Carmen Sessa. 1991. The membership problem for unmixed polynomial ideals is solvable in single exponential time. Discrete Applied Mathematics 33 1 (1991) 73\u201394. 10.1016\/0166-218X(91)90109-A","DOI":"10.1016\/0166-218X(91)90109-A"},{"key":"e_1_3_3_1_10_2","doi-asserted-by":"publisher","unstructured":"Thomas\u00a0W. Dub\u00e9. 1990. The Structure of Polynomial Ideals and Gr\u00f6bner Bases. SIAM J. Comput. 19 4 (8 1990) 750\u2013773. 10.1137\/0219053","DOI":"10.1137\/0219053"},{"key":"e_1_3_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2012.66"},{"key":"e_1_3_3_1_12_2","doi-asserted-by":"publisher","unstructured":"Andre Galligo and Zbigniew Jelonek. 2020. Elimination ideals and B\u00e9zout relations. Journal of Algebra 562 (2020) 621\u2013626. 10.1016\/j.jalgebra.2020.06.022","DOI":"10.1016\/j.jalgebra.2020.06.022"},{"key":"e_1_3_3_1_13_2","unstructured":"D.\u00a0R. Grayson and M.\u00a0E. Stillman. [n. d.]. Macaulay2 a software system for research in algebraic geometry. Available at http:\/\/www.math.uiuc.edu\/Macaulay2\/. (version 1.24.11)."},{"key":"e_1_3_3_1_14_2","doi-asserted-by":"crossref","unstructured":"Grete Hermann. 1926. Die Frage der endlich vielen Schritte in der Theorie der Polynomideale. Math. Ann. 95 (1926) 736\u2013788.","DOI":"10.1007\/BF01206635"},{"key":"e_1_3_3_1_15_2","volume-title":"An introduction to automata theory, languages, and computation","author":"Hopcroft John\u00a0E","year":"1979","unstructured":"John\u00a0E Hopcroft and Jeffrey\u00a0D Ullman. 1979. An introduction to automata theory, languages, and computation. Pearson."},{"key":"e_1_3_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139856065"},{"key":"e_1_3_3_1_17_2","unstructured":"Daniel\u00a0M. Kane. 2017. Unary Subset-Sum is in Logspace. arxiv:https:\/\/arXiv.org\/abs\/1012.1336\u00a0[cs.CC]"},{"key":"e_1_3_3_1_18_2","unstructured":"Leonie Kayser. 2022. Gr\u00f6bner Bases and Their Complexity. Master\u2019s thesis."},{"key":"e_1_3_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803406"},{"key":"e_1_3_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70628-1"},{"key":"e_1_3_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-28296-3"},{"key":"e_1_3_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/236869.236900"},{"key":"e_1_3_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.5555\/73228.73262"},{"key":"e_1_3_3_1_24_2","doi-asserted-by":"publisher","unstructured":"Ernst\u00a0W. Mayr. 1997. Some Complexity Results for Polynomial Ideals. Journal of Complexity 13 3 (1997) 303\u2013325. 10.1006\/jcom.1997.0447","DOI":"10.1006\/jcom.1997.0447"},{"key":"e_1_3_3_1_25_2","doi-asserted-by":"publisher","unstructured":"Ernst\u00a0W. Mayr and Albert\u00a0R. Meyer. 1982. The complexity of the word problems for commutative semigroups and polynomial ideals. Advances in Mathematics 46 3 (12 1982) 305\u2013329. 10.1016\/0001-8708(82)90048-2","DOI":"10.1016\/0001-8708(82)90048-2"},{"key":"e_1_3_3_1_26_2","doi-asserted-by":"publisher","unstructured":"Ernst\u00a0W. Mayr and Stephan Ritscher. 2013. Dimension-dependent bounds for Gr\u00f6bner bases of polynomial ideals. Journal of Symbolic Computation 49 (2013) 78\u201394. 10.1016\/j.jsc.2011.12.018The International Symposium on Symbolic and Algebraic Computation.","DOI":"10.1016\/j.jsc.2011.12.018"},{"key":"e_1_3_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-70566-820"},{"key":"e_1_3_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0085537"},{"key":"e_1_3_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_3_3_1_30_2","doi-asserted-by":"publisher","unstructured":"David Shannon and Moss Sweedler. 1988. Using Gr\u00f6bner bases to determine algebra membership split surjective algebra homomorphisms determine birational equivalence. Journal of Symbolic Computation 6 2 (1988) 267\u2013273. 10.1016\/S0747-7171(88)80047-6","DOI":"10.1016\/S0747-7171(88)80047-6"},{"key":"e_1_3_3_1_31_2","unstructured":"David Spear. 1977. A constructive approach to commutative ring theory. https:\/\/api.semanticscholar.org\/CorpusID:117037310"},{"key":"e_1_3_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03927-4"}],"event":{"name":"ISSAC '25: International Symposium on Symbolic and Algebraic Computation","sponsor":["SIGSAM ACM Special Interest Group on Symbolic and Algebraic Manipulation"],"location":"Guanajuato Mexico","acronym":"ISSAC '25"},"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.3747578","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T11:39:33Z","timestamp":1762774773000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3747199.3747578"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,28]]},"references-count":31,"alternative-id":["10.1145\/3747199.3747578","10.1145\/3747199"],"URL":"https:\/\/doi.org\/10.1145\/3747199.3747578","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"}}]}}