{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:25:40Z","timestamp":1787340340434,"version":"build-2736575974"},"reference-count":37,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>Each symmetric matrix $\\mathbf{A}$ over $\\mathbb{C}$ defines a graph homomorphism function $Z_{\\bf A}(\\cdot)$ on undirected graphs. The function $Z_{\\mathbf{A}} (\\cdot)$ is also called the partition function from statistical physics, and can encode many interesting graph properties, including counting vertex covers and $k$-colorings. We study the computational complexity of $Z_{\\mathbf{A}} (\\cdot)$ for arbitrary symmetric matrices $\\mathbf{A}$ with algebraic complex values. Building on work by Dyer and Greenhill [Random Structures and Algorithms, 17 (2000), pp. 260--289], Bulatov and Grohe [Theoretical Computer Science, 348 (2005), pp. 148--186], and especially the recent beautiful work by Goldberg et al. [SIAM J. Comput., 39 (2010), pp. 3336--3402], we prove a complete dichotomy theorem for this problem. We show that $Z_{\\mathbf{A}} (\\cdot)$ is either computable in polynomial-time or \\#P-hard, depending explicitly on the matrix $\\mathbf{A}$. We further prove that the tractability criterion on $\\mathbf{A}$ is polynomial-time decidable.<\/jats:p>","DOI":"10.1137\/110840194","type":"journal-article","created":{"date-parts":[[2013,5,21]],"date-time":"2013-05-21T14:15:40Z","timestamp":1369145740000},"page":"924-1029","source":"Crossref","is-referenced-by-count":46,"title":["Graph Homomorphisms with Complex Values: A Dichotomy Theorem"],"prefix":"10.1137","volume":"42","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xi","family":"Chen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,5,21]]},"reference":[{"key":"atypb1","first-page":"646","author":"Bulatov A.","year":"2008","journal-title":"Languages and Programming"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"A. Bulatov,\n                      The Complexity of the Counting Constraint Satisfaction Problem\n                      , Electronic Colloquium on Computational Complexity, 2009.","DOI":"10.1007\/978-3-540-70575-8_53"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.12.002"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.011"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"J.Y. Cai and X. Chen,\n                      A decidable dichotomy theorem on directed graph homomorphisms with nonnegative weights\n                      , in Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, 2010, pp. 437-446.","DOI":"10.1109\/FOCS.2010.49"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"J.Y. Cai and X. Chen,\n                      Complexity of counting CSP with complex weights\n                      , in Proceedings of the 44th Symposium on Theory of Computing, 2012, pp. 909-920.","DOI":"10.1145\/2213977.2214059"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"J.Y. Cai, X. Chen, and P. Lu,\n                      Non-negatively weighted \\#CSPs: An effective complexity dichotomy\n                      , in Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011.","DOI":"10.1109\/CCC.2011.32"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"J.Y. Cai and P. Lu,\n                      Holographic algorithms: From art to science\n                      , in Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007, pp. 401-410.","DOI":"10.1145\/1250790.1250850"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"J.Y. Cai, P. Lu, and M. Xia,\n                      Holant problems and counting CSP\n                      , in Proceedings of the 41st ACM Symposium on Theory of Computing, 2009, pp. 715-724.","DOI":"10.1145\/1536414.1536511"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.4064\/aa-16-2-179-194"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"N. Creignou, S. Khanna, and M. Sudan,\n                      Complexity Classifications of Boolean Constraint Satisfaction Problems\n                      , SIAM Monogr. Discrete Math. Appl., SIAM, Philadelphia, 2001.","DOI":"10.1137\/1.9780898718546"},{"key":"atypb12","first-page":"54","author":"Dyer M. E.","year":"2007","journal-title":"J. ACM"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"M. E. Dyer and D. M. Richerby,\n                      On the complexity of \\#CSP\n                      , in Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010, pp. 725-734.","DOI":"10.1145\/1806689.1806789"},{"key":"atypb15","unstructured":"A. Ehrenfeucht and M. Karpinski,\n                      The Computational Complexity of (XOR, AND)-Counting Problems\n                      , Tech. report TR-8543, Universit\u00e4t Bonn, 1990."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"atypb17","unstructured":"R. Feynman, R. Leighton, and M. Sands,\n                      The Feynman Lectures on Physics\n                      , Addison-Wesley, Reading, MA, 1970."},{"key":"atypb18","first-page":"37","volume":"20","author":"Freedman M.","year":"2007","journal-title":"J. AMS"},{"key":"atypb19","unstructured":"G. Ge,\n                      Algorithms Related to Multiplicative Representations of Algebraic Numbers\n                      , Ph.D. thesis, University of California-Berkeley, 1993."},{"key":"atypb20","unstructured":"G. Ge,\n                      Testing equalities of multiplicative representations in polynomial time\n                      , in Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, 1993, pp. 422-\u00d0426."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/090757496"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"P. Hell and J. Ne\u0161et\u0159il,\n                      Graphs and Homomorphisms\n                      , Oxford University Press, New York, 2004.","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"atypb24","unstructured":"N. Jacobson,\n                      Basic Algebra\n                      I, W.H. Freeman, New York, 1985."},{"key":"atypb25","unstructured":"S. Lang,\n                      Algebra\n                      , 3rd ed., Springer-Verlag, New York, 2002."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1992-00284-7"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"R. Lidl and H. Niederreiter,\n                      Finite Fields\n                      , Encyclopedia Math. Appl., Cambridge University Press, Cambridge, UK, 1997.","DOI":"10.1017\/CBO9780511525926"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/BF02280291"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2005.04.012"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"P. Morandi,\n                      Field and Galois Theory\n                      , Grad. Texts in Math. 167, Springer, New York, 1996.","DOI":"10.1007\/978-1-4612-4040-2"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"T.J. Schaefer,\n                      The complexity of satisfiability problems\n                      , in Proceedings of the 10th Annual ACM Symposium on Theory of Computing, 1978, pp. 216-226.","DOI":"10.1145\/800133.804350"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.10.003"},{"key":"atypb33","unstructured":"M. Thurley,\n                      The Complexity of Partition Functions\n                      , Ph.D. thesis, Humboldt Universit\u00e4t zu Berlin, 2009."},{"key":"atypb34","unstructured":"M. Thurley,\n                      The Complexity of Partition Functions on Hermitian Matrices\n                      , arXiv:1004.0992, 2010."},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.34"},{"key":"atypb36","first-page":"509","author":"Valiant L. G.","year":"2006","journal-title":"Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1137\/070682575"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/110840194","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:30:53Z","timestamp":1787337053000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/110840194"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/110840194"],"URL":"https:\/\/doi.org\/10.1137\/110840194","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}