{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:17:59Z","timestamp":1750220279838,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":32,"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.3520075","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"1024-1037","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Complexity classification of counting graph homomorphisms modulo a prime number"],"prefix":"10.1145","author":[{"given":"Andrei A.","family":"Bulatov","sequence":"first","affiliation":[{"name":"Simon Fraser University, Canada"}]},{"given":"Amirhossein","family":"Kazeminia","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","volume-title":"Dagstuhl Follow-Ups","volume":"7","author":"Barto Libor","year":"2017","unstructured":"Libor Barto , Andrei Krokhin , and Ross Willard . 2017 . Polymorphisms, and how to use them . In Dagstuhl Follow-Ups , Vol. 7 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Libor Barto, Andrei Krokhin, and Ross Willard. 2017. Polymorphisms, and how to use them. In Dagstuhl Follow-Ups, Vol. 7. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"volume-title":"Combinatorics and Complexity of Partition Functions. Algorithms and combinatorics","author":"Barvinok Alexander I.","key":"e_1_3_2_1_2_1","unstructured":"Alexander I. Barvinok . 2016. Combinatorics and Complexity of Partition Functions. Algorithms and combinatorics , Vol. 30 . Springer . Alexander I. Barvinok. 2016. Combinatorics and Complexity of Partition Functions. Algorithms and combinatorics, Vol. 30. Springer."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528400"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.09.005"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.011"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_3_2_1_7_1","first-page":"229","volume-title":"On the Power of Parity Polynomial Time. In STACS 1989 (Lecture Notes in Computer Science","volume":"349","author":"Hemachandra Cai","unstructured":"Jin-yi Cai and Lane A. Hemachandra . 1989 . On the Power of Parity Polynomial Time. In STACS 1989 (Lecture Notes in Computer Science , Vol. 349 ) 229 - 239 . Jin-yi Cai and Lane A. Hemachandra. 1989. On the Power of Parity Polynomial Time. In STACS 1989 (Lecture Notes in Computer Science, Vol. 349 ) 229-239."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Nadia Creignou and Miki Hermann. 1996. Complexity of Generalized Satisfiability Counting Problems. Inf. Comput. 125 1 ( 1996 ) 1-12.   Nadia Creignou and Miki Hermann. 1996. Complexity of Generalized Satisfiability Counting Problems. Inf. Comput. 125 1 ( 1996 ) 1-12.","DOI":"10.1006\/inco.1996.0016"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.08.008"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"M. Dyer and C. Greenhill. 2000. The complexity of counting graph homomorphisms. Random Structures and Algorithms 17 ( 2000 ) 260-289.   M. Dyer and C. Greenhill. 2000. The complexity of counting graph homomorphisms. Random Structures and Algorithms 17 ( 2000 ) 260-289.","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1314690.1314691"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/100811258"},{"key":"e_1_3_2_1_13_1","unstructured":"John Faben. 2008. The complexity of counting solutions to Generalised Satisfiability Problems modulo k. arXiv:0809. 1836 [cs.CC]   John Faben. 2008. The complexity of counting solutions to Generalised Satisfiability Problems modulo k. arXiv:0809. 1836 [cs.CC]"},{"key":"e_1_3_2_1_14_1","unstructured":"John Faben and Mark Jerrum. 2013. The complexity of parity graph homomorphism: an initial investigation. arXiv preprint arXiv:1309.4033 ( 2013 ).   John Faben and Mark Jerrum. 2013. The complexity of parity graph homomorphism: an initial investigation. arXiv preprint arXiv:1309.4033 ( 2013 )."},{"key":"e_1_3_2_1_15_1","volume-title":"Vardi","author":"Feder Tom\u00e1s","year":"1998","unstructured":"Tom\u00e1s Feder and Moshe Y . Vardi . 1998 . The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory. SIAM J. Comput . 28, 1 ( 1998 ), 57-104. Tom\u00e1s Feder and Moshe Y. Vardi. 1998. The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory. SIAM J. Comput. 28, 1 ( 1998 ), 57-104."},{"key":"e_1_3_2_1_16_1","volume-title":"Marc Roth, and Stanislav Zivney.","author":"Focke Jacob","year":"2020","unstructured":"Jacob Focke , Leslie Ann Goldberg , Marc Roth, and Stanislav Zivney. 2020 . Counting Homomorphisms to 4-minor-free Graphs, modulo 2. CoRR abs\/ 2006.16632 ( 2020 ). arXiv: 2006. 16632 [cs.CC] Jacob Focke, Leslie Ann Goldberg, Marc Roth, and Stanislav Zivney. 2020. Counting Homomorphisms to 4-minor-free Graphs, modulo 2. CoRR abs\/ 2006.16632 ( 2020 ). arXiv: 2006. 16632 [cs.CC]"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.137"},{"key":"e_1_3_2_1_18_1","article-title":"Counting homomorphisms to square-free graphs, modulo 2","volume":"8","author":"G\u00f6bel Andreas","year":"2016","unstructured":"Andreas G\u00f6bel , Leslie Ann Goldberg , and David Richerby . 2016 . Counting homomorphisms to square-free graphs, modulo 2 . ACM Transactions on Computation Theory (TOCT) 8 , 3 ( 2016 ), 1-29. Andreas G\u00f6bel, Leslie Ann Goldberg, and David Richerby. 2016. Counting homomorphisms to square-free graphs, modulo 2. ACM Transactions on Computation Theory (TOCT) 8, 3 ( 2016 ), 1-29.","journal-title":"ACM Transactions on Computation Theory (TOCT)"},{"key":"e_1_3_2_1_19_1","volume-title":"MFCS","author":"G\u00f6bel Andreas","year":"2018","unstructured":"Andreas G\u00f6bel , J. A. Gregor Lagodzinski , and Karen Seidel . 2018 . Counting homomorphisms to trees modulo a prime . In MFCS 2018), 49 : 1-49 : 13. Andreas G\u00f6bel, J. A. Gregor Lagodzinski, and Karen Seidel. 2018. Counting homomorphisms to trees modulo a prime. In MFCS 2018), 49 : 1-49 : 13."},{"key":"e_1_3_2_1_20_1","first-page":"249","volume-title":"STACS","author":"Guo Heng","year":"2011","unstructured":"Heng Guo , Sangxia Huang , Pinyan Lu , and Mingji Xia . 2011 . The Complexity of Weighted Boolean #CSP Modulo k . In STACS 2011), 249 - 260 . Heng Guo, Sangxia Huang, Pinyan Lu, and Mingji Xia. 2011. The Complexity of Weighted Boolean #CSP Modulo k. In STACS 2011), 249-260."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2635825"},{"key":"e_1_3_2_1_22_1","volume-title":"Handbook of Product Graphs","author":"Hammack Richard","unstructured":"Richard Hammack , Wilfried Imrich , and Sandi Klavzar . 2011. Handbook of Product Graphs , Second Edition (2 nd ed.). CRC Press, Inc. , USA. Richard Hammack, Wilfried Imrich, and Sandi Klavzar. 2011. Handbook of Product Graphs, Second Edition (2nd ed.). CRC Press, Inc., USA.","edition":"2"},{"volume-title":"Graphs and homomorphisms. Oxford Lecture Series in Mathematics and its Applications","author":"Hell P.","key":"e_1_3_2_1_23_1","unstructured":"P. Hell and Ne\u0161et\u0159il. 2004. Graphs and homomorphisms. Oxford Lecture Series in Mathematics and its Applications , Vol. 28 . Oxford University Press . P. Hell and Ne\u0161et\u0159il. 2004. Graphs and homomorphisms. Oxford Lecture Series in Mathematics and its Applications, Vol. 28. Oxford University Press."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Ulrich Hertrampf. 1990. Relations Among Mod-Classes. Theor. Comput. Sci. 74 3 ( 1990 ) 325-328.   Ulrich Hertrampf. 1990. Relations Among Mod-Classes. Theor. Comput. Sci. 74 3 ( 1990 ) 325-328.","DOI":"10.1016\/0304-3975(90)90081-R"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00230-2"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222066"},{"key":"e_1_3_2_1_27_1","volume-title":"MFCS","author":"Kazeminia Amirhossein","year":"2019","unstructured":"Amirhossein Kazeminia and Andrei A Bulatov . 2019 . Counting Homomorphisms Modulo a Prime Number . In MFCS 2019), 59 : 1-59 : 13. Amirhossein Kazeminia and Andrei A Bulatov. 2019. Counting Homomorphisms Modulo a Prime Number. In MFCS 2019), 59 : 1-59 : 13."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24674-9_1"},{"key":"e_1_3_2_1_29_1","volume-title":"CoRR abs\/","author":"Gregor Lagodzinski J. A.","year":"2011","unstructured":"J. A. Gregor Lagodzinski , Andreas G\u00f6bel , Katrin Casel , and Tobias Friedrich . 2021. On Counting (Quantum-) Graph Homomorphisms in Finite Fields of Prime Order . CoRR abs\/ 2011 .04827 ( 2021 ). arXiv: 2011. 04827 [cs.CC] J. A. Gregor Lagodzinski, Andreas G\u00f6bel, Katrin Casel, and Tobias Friedrich. 2021. On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order. CoRR abs\/ 2011.04827 ( 2021 ). arXiv: 2011. 04827 [cs.CC]"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"E.H. Lieb and A.D. Sokal. 1981. A general Lee-Yang theorem for one-component and multicomponent ferromagnets. Communications in Mathematical Physics 80 2 ( 1981 ) 153-179.   E.H. Lieb and A.D. Sokal. 1981. A general Lee-Yang theorem for one-component and multicomponent ferromagnets. Communications in Mathematical Physics 80 2 ( 1981 ) 153-179.","DOI":"10.1007\/BF01213009"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"L. Valiant. 1979. The complexity of computing the permanent. Theoretical Computing Science 8 ( 1979 ) 189-201.   L. Valiant. 1979. The complexity of computing the permanent. Theoretical Computing Science 8 ( 1979 ) 189-201.","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"e_1_3_2_1_32_1","series-title":"SIAM Journal on Computing 8 3 ( 1979 ), 410-421","volume-title":"The complexity of enumeration and reliability problems","author":"Valiant L.","unstructured":"L. Valiant . 1979. The complexity of enumeration and reliability problems . SIAM Journal on Computing 8 3 ( 1979 ), 410-421 . L. Valiant. 1979. The complexity of enumeration and reliability problems. SIAM Journal on Computing 8 3 ( 1979 ), 410-421."}],"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.3520075","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520075","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:16Z","timestamp":1750188676000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520075"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":32,"alternative-id":["10.1145\/3519935.3520075","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520075","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"}}]}}