{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T12:23:40Z","timestamp":1764937420963,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":45,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3520063","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"436-449","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["On the complexity of CSP-based ideal membership problems"],"prefix":"10.1145","author":[{"given":"Andrei A.","family":"Bulatov","sequence":"first","affiliation":[{"name":"Simon Fraser University, Canada"}]},{"given":"Akbar","family":"Rafiey","sequence":"additional","affiliation":[{"name":"Simon Fraser University, Canada"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73420-8_26"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3265985"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2677161.2677165"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1017\/bsl.2015.25"},{"key":"e_1_3_2_1_5_1","volume-title":"Andrei A. Krokhin and Stanislav Zivn\u00fd (Eds.) (Dagstuhl Follow-Ups","volume":"44","author":"Barto Libor","year":"2017","unstructured":"Libor Barto , Andrei A. Krokhin , and Ross Willard . 2017 . Polymorphisms, and How to Use Them. In The Constraint Satisfaction Problem: Complexity and Approximability , Andrei A. Krokhin and Stanislav Zivn\u00fd (Eds.) (Dagstuhl Follow-Ups , Vol. 7). 1\u2013 44 . Libor Barto, Andrei A. Krokhin, and Ross Willard. 2017. Polymorphisms, and How to Use Them. In The Constraint Satisfaction Problem: Complexity and Approximability, Andrei A. Krokhin and Stanislav Zivn\u00fd (Eds.) (Dagstuhl Follow-Ups, Vol. 7). 1\u201344."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365714"},{"volume-title":"Gr\u00f6bner Bases","author":"Becker Thomas","key":"e_1_3_2_1_7_1","unstructured":"Thomas Becker and Volker Weispfenning . 1993. Gr\u00f6bner bases . In Gr\u00f6bner Bases . Springer , 187\u2013242. Thomas Becker and Volker Weispfenning. 1993. Gr\u00f6bner bases. In Gr\u00f6bner Bases. Springer, 187\u2013242."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2020.13"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2021.16"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2005.09.007"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.37"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.09.005"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_3_2_1_14_1","volume-title":"Bulatov and Akbar Rafiey","author":"Andrei","year":"2020","unstructured":"Andrei A. Bulatov and Akbar Rafiey . 2020 . On the Complexity of CSP-based Ideal Membership Problems. CoRR , abs\/2011.03700 (2020). Andrei A. Bulatov and Akbar Rafiey. 2020. On the Complexity of CSP-based Ideal Membership Problems. CoRR, abs\/2011.03700 (2020)."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2022.18"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"S. Burris and H.P. Sankappanavar. 1981. A course in universal algebra (Graduate Texts in Mathematics Vol. 78). Springer-Verlag New York-Berlin.  S. Burris and H.P. Sankappanavar. 1981. A course in universal algebra (Graduate Texts in Mathematics Vol. 78). Springer-Verlag New York-Berlin.","DOI":"10.1007\/978-1-4613-8130-3"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.1996.507685"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237860"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)90021-3"},{"volume-title":"varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra","author":"Cox David","key":"e_1_3_2_1_20_1","unstructured":"David Cox , John Little , and Donal O Shea . 2013. Ideals , varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra . Springer Science & Business Media . David Cox, John Little, and Donal OShea. 2013. Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra. Springer Science & Business Media."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(91)90109-A"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1993.1051"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743515"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01206635"},{"key":"e_1_3_2_1_26_1","volume-title":"Ueber die Theorie der algebraischen Formen. Mathematische annalen, 36, 4","author":"Hilbert David","year":"1890","unstructured":"David Hilbert . 1890. Ueber die Theorie der algebraischen Formen. Mathematische annalen, 36, 4 ( 1890 ), 473\u2013534. David Hilbert. 1890. Ueber die Theorie der algebraischen Formen. Mathematische annalen, 36, 4 (1890), 473\u2013534."},{"key":"e_1_3_2_1_27_1","volume-title":"\u00dcber die vollen Invariantensysteme. Mathematische annalen, 42, 3","author":"Hilbert David","year":"1893","unstructured":"David Hilbert . 1893. \u00dcber die vollen Invariantensysteme. Mathematische annalen, 42, 3 ( 1893 ), 313\u2013373. David Hilbert. 1893. \u00dcber die vollen Invariantensysteme. Mathematische annalen, 42, 3 (1893), 313\u2013373."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-013-9365-7"},{"key":"e_1_3_2_1_30_1","volume-title":"Vardi","author":"Kolaitis Phokion G.","year":"1998","unstructured":"Phokion G. Kolaitis and Moshe Y . Vardi . 1998 . Conjunctive-Query Containment and Constraint Satisfaction. In ACM SIGACT-SIGMOD-SIGART. ACM Press , 205\u2013213. Phokion G. Kolaitis and Moshe Y. Vardi. 1998. Conjunctive-Query Containment and Constraint Satisfaction. In ACM SIGACT-SIGMOD-SIGART. ACM Press, 205\u2013213."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3449350"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0029002"},{"key":"e_1_3_2_1_33_1","volume-title":"The complexity of the word problems for commutative semigroups and polynomial ideals. Advances in mathematics, 46, 3","author":"Mayr Ernst W","year":"1982","unstructured":"Ernst W Mayr and Albert R Meyer . 1982. The complexity of the word problems for commutative semigroups and polynomial ideals. Advances in mathematics, 46, 3 ( 1982 ), 305\u2013329. Ernst W Mayr and Albert R Meyer. 1982. The complexity of the word problems for commutative semigroups and polynomial ideals. Advances in mathematics, 46, 3 (1982), 305\u2013329."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Ralph N McKenzie George F McNulty and Walter F Taylor. 2018. Algebras lattices varieties. 383 American Mathematical Soc..  Ralph N McKenzie George F McNulty and Walter F Taylor. 2018. Algebras lattices varieties. 383 American Mathematical Soc..","DOI":"10.1090\/chel\/383.H"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2017.59"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-39.1.723"},{"volume-title":"Interpolation and approximation by polynomials. 14","author":"Phillips George M","key":"e_1_3_2_1_37_1","unstructured":"George M Phillips . 2003. Interpolation and approximation by polynomials. 14 , Springer Science & Business Media . George M Phillips. 2003. Interpolation and approximation by polynomials. 14, Springer Science & Business Media."},{"volume-title":"The two-valued iterative systems of mathematical logic. Number 5 in Annals of Math. Studies","author":"Post EL","key":"e_1_3_2_1_38_1","unstructured":"EL Post . 1941. The two-valued iterative systems of mathematical logic. Number 5 in Annals of Math. Studies . Princeton Univ. Press . EL Post. 1941. The two-valued iterative systems of mathematical logic. Number 5 in Annals of Math. Studies. Princeton Univ. Press."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2017.80"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1974-0416874-9"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1974-0349648-2"},{"key":"e_1_3_2_1_43_1","unstructured":"\u00c1gnes Szendrei. 1986. Clones in universal algebra. Les presses de L\u2019universite de Montreal.  \u00c1gnes Szendrei. 1986. Clones in universal algebra. Les presses de L\u2019universite de Montreal."},{"volume-title":"Department of Computer Science","author":"van Dongen Marc R.C.","key":"e_1_3_2_1_44_1","unstructured":"Marc R.C. van Dongen . 2002. Constraints, Varieties, and Algorithms. Ph. D. Dissertation . Department of Computer Science , University College , Cork, Ireland . http:\/\/csweb.ucc.ie\/~dongen\/papers\/UCC\/02\/thesis.pdf Marc R.C. van Dongen. 2002. Constraints, Varieties, and Algorithms. Ph. D. Dissertation. Department of Computer Science, University College, Cork, Ireland. http:\/\/csweb.ucc.ie\/~dongen\/papers\/UCC\/02\/thesis.pdf"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.38"}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Rome Italy","acronym":"STOC '22"},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520063","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520063","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:15Z","timestamp":1750188675000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520063"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":45,"alternative-id":["10.1145\/3519935.3520063","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520063","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}