{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T05:13:14Z","timestamp":1777957994339,"version":"3.51.4"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"name":"NSERC Discovery"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>\n                    Given polynomials\n                    <jats:italic toggle=\"yes\">f<\/jats:italic>\n                    <jats:sub>0<\/jats:sub>\n                    ,\n                    <jats:italic toggle=\"yes\">f<\/jats:italic>\n                    <jats:sub>1<\/jats:sub>\n                    , \u2026,\n                    <jats:italic toggle=\"yes\">\n                      f\n                      <jats:sub>k<\/jats:sub>\n                    <\/jats:italic>\n                    the Ideal Membership Problem, IMP for short, asks if\n                    <jats:italic toggle=\"yes\">f<\/jats:italic>\n                    <jats:sub>0<\/jats:sub>\n                    belongs to the ideal generated by\n                    <jats:italic toggle=\"yes\">f<\/jats:italic>\n                    <jats:sub>1<\/jats:sub>\n                    , \u2026,\n                    <jats:italic toggle=\"yes\">\n                      f\n                      <jats:sub>k<\/jats:sub>\n                    <\/jats:italic>\n                    . In the search version of this problem, the task is to find a proof of this fact. The IMP is a well-known fundamental problem with numerous applications. For instance, it underlies many proof systems based on polynomials such as Nullstellensatz, Polynomial Calculus, and Sum-of-Squares. Although the IMP is in general intractable, in many important cases it can be efficiently solved.\n                  <\/jats:p>\n                  <jats:p>\n                    Mastrolilli [SODA\u201919] initiated a systematic study of IMPs for ideals arising from Constraint Satisfaction Problems (CSPs), parameterized by constraint languages, denoted IMP(\u0393). The ultimate goal of this line of research is to classify all such IMPs accordingly to their complexity. Mastrolilli achieved this goal for IMPs arising from CSP(\u0393) where \u0393 is a Boolean constraint language, while Bulatov and Rafiey [STOC\u201922] advanced these results to several cases of CSPs over finite domains. In this article, we consider IMPs arising from CSPs over \u201caffine\u201d constraint languages, in which constraints are subgroups (or their cosets) of direct products of Abelian groups. This kind of CSPs include systems of linear equations and are considered one of the most important types of tractable CSPs. Some special cases of the problem have been considered before by Bharathi and Mastrolilli [MFCS\u201921] for linear equations modulo 2, and by Bulatov and Rafiey [STOC\u201922] for systems of linear equations over\n                    <jats:sans-serif>GF<\/jats:sans-serif>\n                    (\n                    <jats:italic toggle=\"yes\">p<\/jats:italic>\n                    ),\n                    <jats:italic toggle=\"yes\">p<\/jats:italic>\n                    prime. Here, we prove that if \u0393 is an affine constraint language then IMP(\u0393) is solvable in polynomial time assuming the input polynomial has bounded degree.\n                  <\/jats:p>","DOI":"10.1145\/3797909","type":"journal-article","created":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T04:37:35Z","timestamp":1777955855000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The Ideal Membership Problem and Abelian Groups"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5516-1704","authenticated-orcid":false,"given":"Andrei","family":"Bulatov","sequence":"first","affiliation":[{"name":"School of Computer Science, Simon Fraser University","place":["Burnaby, Canada"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1619-3997","authenticated-orcid":false,"given":"Akbar","family":"Rafiey","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, New York University","place":["Brooklyn, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,5,4]]},"reference":[{"issue":"1","key":"e_1_3_2_2_2","first-page":"1:1\u20131:46","article-title":"Proof complexity meets algebra","volume":"20","author":"Atserias Albert","year":"2019","unstructured":"Albert Atserias and Joanna Ochremiak. 2019. Proof complexity meets algebra. ACM Transactions on Computational Logic 20, 1 (2019), 1:1\u20131:46.","journal-title":"ACM Transactions on Computational Logic"},{"issue":"1","key":"e_1_3_2_3_2","first-page":"3:1\u20133:19","article-title":"Constraint satisfaction problems solvable by local consistency methods","volume":"61","author":"Barto Libor","year":"2014","unstructured":"Libor Barto and Marcin Kozik. 2014. Constraint satisfaction problems solvable by local consistency methods. Journal of the ACM 61, 1 (2014), 3:1\u20133:19.","journal-title":"Journal of the ACM"},{"key":"e_1_3_2_4_2","series-title":"Dagstuhl Follow-Ups","first-page":"1","volume-title":"Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability.","author":"Barto Libor","year":"2017","unstructured":"Libor Barto, Andrei A. Krokhin, and Ross Willard. 2017. Polymorphisms, and how to use them. In Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability.Andrei A. Krokhin and Stanislav Zivn\u00fd (Eds.), Dagstuhl Follow-Ups. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 1\u201344."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365714"},{"key":"e_1_3_2_6_2","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/978-1-4612-0913-3_6","volume-title":"Proceedings of the Gr\u00f6bner Bases","author":"Becker Thomas","year":"1993","unstructured":"Thomas Becker and Volker Weispfenning. 1993. Gr\u00f6bner bases. In Proceedings of the Gr\u00f6bner Bases. Springer, 187\u2013242."},{"key":"e_1_3_2_7_2","unstructured":"Arpitha P. Bharathi and Monaldo Mastrolilli. 2020. Ideal membership problem for Boolean minority. arxiv:2006.16422. Retrieved from https:\/\/arxiv.org\/abs\/2006.16422"},{"key":"e_1_3_2_8_2","first-page":"16:1\u201316:20","volume-title":"Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science","author":"Bharathi Arpitha P.","year":"2021","unstructured":"Arpitha P. Bharathi and Monaldo Mastrolilli. 2021. Ideal membership problem for Boolean minority and dual discriminator. In Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science. 16:1\u201316:20."},{"key":"e_1_3_2_9_2","doi-asserted-by":"crossref","unstructured":"V. G. Bodnarchuk L. A. Kaluzhnin V. N. Kotov and B. A. Romov. 1969. Galois theory for Post algebras. I. Cybernetics 5 3 (1969) 243\u2013252.","DOI":"10.1007\/BF01070906"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2005.09.007"},{"key":"e_1_3_2_11_2","first-page":"319","volume-title":"Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science","author":"Bulatov Andrei A.","year":"2017","unstructured":"Andrei A. Bulatov. 2017. A dichotomy theorem for nonuniform CSPs. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science. Chris Umans (Ed.), IEEE Computer Society, 319\u2013330."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/050628957"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45193-8_13"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_3_2_15_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/978-3-540-92800-3_5","volume-title":"Proceedings of the Complexity of Constraints - An Overview of Current Research Themes [Result of a Dagstuhl Seminar].","volume":"5250","author":"Bulatov Andrei A.","year":"2008","unstructured":"Andrei A. Bulatov, Andrei A. Krokhin, and Beno\u00eet Larose. 2008. Dualities for constraint satisfaction problems. In Proceedings of the Complexity of Constraints - An Overview of Current Research Themes [Result of a Dagstuhl Seminar].Nadia Creignou, Phokion G. Kolaitis, and Heribert Vollmer (Eds.), Lecture Notes in Computer Science, Vol. 5250, Springer, 93\u2013124."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.STACS.2022.18"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520063"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.1996.507685"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237860"},{"key":"e_1_3_2_20_2","volume-title":"Ideals, Varieties, and Algorithms: an Introduction to Computational Algebraic Geometry and Commutative Algebra","author":"Cox David","year":"2013","unstructured":"David Cox, John Little, and Donal OShea. 2013. Ideals, Varieties, and Algorithms: an Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer Science and Business Media."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(91)90109-A"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_3_2_23_2","doi-asserted-by":"crossref","unstructured":"David Geiger. 1968. Closed systems of functions and predicates. Pacific Journal of Mathematics 27 1 (1968) 95\u2013100.","DOI":"10.2140\/pjm.1968.27.95"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743515"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01206635"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/090775646"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-013-9365-7"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.29"},{"issue":"4","key":"e_1_3_2_30_2","first-page":"32:1\u201332:29","article-title":"The complexity of the ideal membership problem for constrained problems over the boolean domain","volume":"17","author":"Mastrolilli Monaldo","year":"2021","unstructured":"Monaldo Mastrolilli. 2021. The complexity of the ideal membership problem for constrained problems over the boolean domain. ACM Transactions on Algorithms 17, 4 (2021), 32:1\u201332:29.","journal-title":"ACM Transactions on Algorithms"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0029002"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(82)90048-2"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2017.59"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2017.80"},{"issue":"2","key":"e_1_3_2_35_2","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1090\/S0002-9939-1974-0416874-9","article-title":"Constructive aspects of noetherian rings","volume":"44","author":"Richman Fred","year":"1974","unstructured":"Fred Richman. 1974. Constructive aspects of noetherian rings. Proceedings of the American Mathematical Society 44, 2 (1974), 436\u2013441.","journal-title":"Proceedings of the American Mathematical Society"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1974-0349648-2"},{"issue":"3","key":"e_1_3_2_37_2","first-page":"12:1\u201312:22","article-title":"The limits of SDP relaxations for general-valued CSPs","volume":"10","author":"Thapper Johan","year":"2018","unstructured":"Johan Thapper and Stanislav Zivn\u00fd. 2018. The limits of SDP relaxations for general-valued CSPs. ACM Transactions on Computation Theory 10, 3 (2018), 12:1\u201312:22.","journal-title":"ACM Transactions on Computation Theory"},{"key":"e_1_3_2_38_2","volume-title":"Constraints, Varieties, and Algorithms","author":"Dongen Marc R.C. van","year":"2002","unstructured":"Marc R.C. van Dongen. 2002. Constraints, Varieties, and Algorithms. Ph. D. Dissertation. Department of Computer Science, University College, Cork, Ireland. Retrieved from http:\/\/csweb.ucc.ie\/dongen\/papers\/UCC\/02\/thesis.pdf"},{"key":"e_1_3_2_39_2","first-page":"331","volume-title":"Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science.","author":"Zhuk Dmitriy","year":"2017","unstructured":"Dmitriy Zhuk. 2017. A proof of CSP dichotomy conjecture. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science.Chris Umans (Ed.), IEEE Computer Society, 331\u2013342."},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3402029"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3797909","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T04:37:39Z","timestamp":1777955859000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3797909"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,4]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1145\/3797909"],"URL":"https:\/\/doi.org\/10.1145\/3797909","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,4]]},"assertion":[{"value":"2024-12-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-01-21","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-05-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}