{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T16:27:43Z","timestamp":1770740863222,"version":"3.49.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,6,16]],"date-time":"2017-06-16T00:00:00Z","timestamp":1497571200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-0914969, CCF-1217549, CCF-1149257 and CCF-1423100"],"award-info":[{"award-number":["CCF-0914969, CCF-1217549, CCF-1149257 and CCF-1423100"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006474","name":"Columbia University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006474","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2017,6,30]]},"abstract":"<jats:p>\n            We give a complexity dichotomy theorem for the counting constraint satisfaction problem (#CSP in short) with algebraic complex weights. To this end, we give three conditions for its tractability. Let\n            <jats:italic>F<\/jats:italic>\n            be any finite set of algebraic complex-valued functions defined on an arbitrary finite domain. We show that #CSP(\n            <jats:italic>F<\/jats:italic>\n            ) is solvable in polynomial time if all three conditions are satisfied and is #P-hard otherwise.\n          <\/jats:p>\n          <jats:p>\n            Our dichotomy theorem generalizes a long series of important results on counting problems and reaches a natural culmination: (a) the problem of counting graph homomorphisms is the special case when\n            <jats:italic>F<\/jats:italic>\n            has a single symmetric binary function [Dyer and Greenhill 2000; Bulatov and Grohe 2005; Goldberg et al. 2010; Cai et al. 2013]; (b) the problem of counting directed graph homomorphisms is the special case when\n            <jats:italic>F<\/jats:italic>\n            has a single but not necessarily symmetric binary function [Dyer et al. 2007; Cai and Chen 2010]; (c) the unweighted form of #CSP is when all functions in\n            <jats:italic>F<\/jats:italic>\n            take values in {0, 1} [Bulatov 2008; Dyer and Richerby 2013].\n          <\/jats:p>","DOI":"10.1145\/2822891","type":"journal-article","created":{"date-parts":[[2017,6,16]],"date-time":"2017-06-16T18:10:59Z","timestamp":1497636659000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":34,"title":["Complexity of Counting CSP with Complex Weights"],"prefix":"10.1145","volume":"64","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[{"name":"University of Wisconsin--Madison and Beijing University, Madison, WI"}]},{"given":"Xi","family":"Chen","sequence":"additional","affiliation":[{"name":"Columbia University"}]}],"member":"320","published-online":{"date-parts":[[2017,6,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/070708093"},{"key":"e_1_2_1_2_1","volume-title":"Exactly Solved Models in Statistical Mechanics","author":"Baxter R. J.","unstructured":"R. J. Baxter . 1982. Exactly Solved Models in Statistical Mechanics . Academic Press , London . R. J. Baxter. 1982. Exactly Solved Models in Statistical Mechanics. Academic Press, London."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120584"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_53"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528400"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/050628957"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.09.005"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.12.002"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.011"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.49"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 4th International Frontiers of Algorithmics Workshop. 148--159","author":"Cai J.-Y.","unstructured":"J.-Y. Cai , X. Chen , R. Lipton , and P. Lu . 2010. On tractable exponential sums . In Proceedings of the 4th International Frontiers of Algorithmics Workshop. 148--159 . J.-Y. Cai, X. Chen, R. Lipton, and P. Lu. 2010. On tractable exponential sums. In Proceedings of the 4th International Frontiers of Algorithmics Workshop. 148--159."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1032314"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/110840194"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0016"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"N. Creignou S. Khanna and M. Sudan. 2001. Complexity Classications of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications.   N. Creignou S. Khanna and M. Sudan. 2001. Complexity Classications of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications.","DOI":"10.1137\/1.9780898718546"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1314690.1314691"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4%3C260::AID-RSA5%3E3.0.CO;2-W"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/100811258"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/090757496"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2008.10.003"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321877"},{"key":"e_1_2_1_24_1","volume-title":"Algorithms in algebraic number theory. Bull. Amer. Math. Soc. 26, 2","author":"Lenstra H. W.","year":"1992","unstructured":"H. W. Lenstra . 1992. Algorithms in algebraic number theory. Bull. Amer. Math. Soc. 26, 2 ( 1992 ). H. W. Lenstra. 1992. Algorithms in algebraic number theory. Bull. Amer. Math. Soc. 26, 2 (1992)."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2822891","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2822891","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2822891","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:48:31Z","timestamp":1750225711000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2822891"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,16]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,6,30]]}},"alternative-id":["10.1145\/2822891"],"URL":"https:\/\/doi.org\/10.1145\/2822891","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,16]]},"assertion":[{"value":"2014-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-06-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}