{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T21:44:04Z","timestamp":1774820644226,"version":"3.50.1"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1714275"],"award-info":[{"award-number":["CCF-1714275"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Science and Technology Innovation 2030","award":["\u201dNew Generation of Artificial Intelligence\u201d Major Project No. 2018AAA0100903"],"award-info":[{"award-number":["\u201dNew Generation of Artificial Intelligence\u201d Major Project No. 2018AAA0100903"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61922052"],"award-info":[{"award-number":["61922052"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100010903","name":"Key Programme","doi-asserted-by":"publisher","award":["61932002"],"award-info":[{"award-number":["61932002"]}],"id":[{"id":"10.13039\/501100010903","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012269","name":"Science and Technology Innovative Research Team in Higher Educational Institutions of Hunan Province","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100012269","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100010903","name":"Key Programme","doi-asserted-by":"publisher","award":["61932002"],"award-info":[{"award-number":["61932002"]}],"id":[{"id":"10.13039\/501100010903","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004739","name":"Youth Innovation Promotion Association of the Chinese Academy of Sciences","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004739","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2020,11]]},"DOI":"10.1007\/s00224-020-09983-8","type":"journal-article","created":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T07:02:44Z","timestamp":1592809364000},"page":"1362-1391","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Dichotomy for Holant\u2217 Problems on the Boolean Domain"],"prefix":"10.1007","volume":"64","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mingji","family":"Xia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"9983_CR1","unstructured":"Backens, M.: A New Holant Dichotomy Inspired by Quantum Computation. In: 44Th International Colloquium on Automata, Languages, and Programming, ICALP 2017, Warsaw, pp. 16:1\u201316:14 (2017)"},{"key":"9983_CR2","unstructured":"Backens, M.: A Complete Dichotomy for Complex-Valued Holantc. In: 45Th International Colloquium on Automata, Languages, and Programming, ICALP 2018, pp. 12:1\u201312:14 (2018)"},{"key":"9983_CR3","volume-title":"Exactly solved models in statistical mechanics","author":"RJ Baxter","year":"1982","unstructured":"Baxter, R. J.: Exactly solved models in statistical mechanics. Academic Press, London (1982)"},{"issue":"5","key":"9983_CR4","first-page":"34:1","volume":"60","author":"AA Bulatov","year":"2013","unstructured":"Bulatov, A. A.: The complexity of the counting constraint satisfaction problem. J. ACM 60(5), 34:1\u201334:41 (2013)","journal-title":"J. ACM"},{"issue":"2","key":"9983_CR5","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1016\/j.jcss.2011.12.002","volume":"78","author":"AA Bulatov","year":"2012","unstructured":"Bulatov, A. A., Dyer, M. E., Goldberg, L. A., Jalsenius, M., Jerrum, M., Richerby, D.: The complexity of weighted and unweighted #CSP. J. Comput. Syst. Sci. 78(2), 681\u2013688 (2012)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2-3","key":"9983_CR6","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/j.tcs.2005.09.011","volume":"348","author":"AA Bulatov","year":"2005","unstructured":"Bulatov, A. A., Grohe, M.: The complexity of partition functions. Theor. Comput. Sci. 348(2-3), 148\u2013186 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9983_CR7","doi-asserted-by":"crossref","unstructured":"Cai, J., Chen, X.: A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-Negative Weights. In: 51Th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, pp 437\u2013446. IEEE Computer Society, Las Vegas (2010)","DOI":"10.1109\/FOCS.2010.49"},{"key":"9983_CR8","doi-asserted-by":"crossref","unstructured":"Cai, J., Chen, X.: Complexity dichotomies for counting problems. Cambridge University Press, Cambridge (2017)","DOI":"10.1017\/9781107477063"},{"issue":"3","key":"9983_CR9","doi-asserted-by":"publisher","first-page":"924","DOI":"10.1137\/110840194","volume":"42","author":"J Cai","year":"2013","unstructured":"Cai, J., Chen, X., Lu, P.: Graph homomorphisms with complex values: a dichotomy theorem. SIAM J. Comput. 42(3), 924\u20131029 (2013)","journal-title":"SIAM J. Comput."},{"key":"9983_CR10","doi-asserted-by":"crossref","unstructured":"Cai, J., Guo, H., Williams, T.: The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems. In: 55Th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, pp. 601\u2013610, Philadelphia (2014)","DOI":"10.1109\/FOCS.2014.70"},{"issue":"1","key":"9983_CR11","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.jcss.2010.06.005","volume":"77","author":"J Cai","year":"2011","unstructured":"Cai, J., Lu, P.: Holographic algorithms: From art to science. J. Comput. Syst. Sci. 77(1), 41\u201361 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"9983_CR12","doi-asserted-by":"crossref","unstructured":"Cai, J., Lu, P., Xia, M.: Dichotomy for Holant* problems of Boolean domain. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pp. 1714\u20131728, San Francisco (2011)","DOI":"10.1137\/1.9781611973082.132"},{"key":"9983_CR13","doi-asserted-by":"crossref","unstructured":"Cai, J., Lu, P., Xia, M.: Dichotomy for Holant* problems with domain size 3. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, pp. 1278\u20131295, New Orleans (2013)","DOI":"10.1137\/1.9781611973105.93"},{"key":"9983_CR14","doi-asserted-by":"crossref","unstructured":"Cai, J., Lu, P., Xia, M.: Dichotomy for real Holantc problems. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pp. 1802\u20131821, New Orleans (2018)","DOI":"10.1137\/1.9781611975031.118"},{"key":"9983_CR15","doi-asserted-by":"crossref","unstructured":"Cai, J. Y., Govorov, A.: Perfect matchings, rank of connection tensors and graph homomorphisms. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201919, pp. 476\u2013495. Society for Industrial and Applied Mathematics, Philadelphia (2019)","DOI":"10.1137\/1.9781611975482.30"},{"key":"9983_CR16","doi-asserted-by":"crossref","unstructured":"Cai, J. Y., Lu, P., Xia, M.: Holographic algorithms by Fibonacci gates and holographic reductions for hardness. In: FOCS \u201908: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society, Washington (2008)","DOI":"10.1109\/FOCS.2008.34"},{"key":"9983_CR17","doi-asserted-by":"crossref","unstructured":"Cai, J. Y., Lu, P., Xia, M.: Holant Problems and Counting CSP. In: Mitzenmacher, M. (ed.) STOC, pp 715\u2013724. ACM (2009)","DOI":"10.1145\/1536414.1536511"},{"issue":"1","key":"9983_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.0016","volume":"125","author":"N Creignou","year":"1996","unstructured":"Creignou, N., Hermann, M.: Complexity of generalized satisfiability counting problems. Inf. Comput. 125(1), 1\u201312 (1996)","journal-title":"Inf. Comput."},{"key":"9983_CR19","doi-asserted-by":"crossref","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classifications of Boolean Constraint Satisfaction Problems. Siam Monographs On Discrete Mathematics And Applications (2001)","DOI":"10.1137\/1.9780898718546"},{"key":"9983_CR20","unstructured":"Dyer, M. E., Goldberg, L. A., Jalsenius, M., Richerby, D.: The Complexity of Approximating Bounded-Degree Boolean #CSP. In: Marion, J., Schwentick, T. (eds.) STACS, LIPIcs, vol. 5, pp 323\u2013334. Schloss Dagstuhl - Leibniz-Zentrum fu\u0307r Informatik (2010)"},{"issue":"5","key":"9983_CR21","doi-asserted-by":"publisher","first-page":"1970","DOI":"10.1137\/070690201","volume":"38","author":"ME Dyer","year":"2009","unstructured":"Dyer, M. E., Goldberg, L. A., Jerrum, M.: The complexity of weighted Boolean #CSP. SIAM J. Comput. 38(5), 1970\u20131986 (2009)","journal-title":"SIAM J. Comput."},{"issue":"3-4","key":"9983_CR22","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/j.jcss.2009.08.003","volume":"76","author":"ME Dyer","year":"2010","unstructured":"Dyer, M. E., Goldberg, L. A., Jerrum, M.: An approximation trichotomy for Boolean #CSP. J. Comput. Syst. Sci. 76(3-4), 267\u2013277 (2010)","journal-title":"J. Comput. Syst. Sci."},{"key":"9983_CR23","doi-asserted-by":"crossref","unstructured":"Dyer, M. E., Goldberg, L. A., Paterson, M.: On counting homomorphisms to directed acyclic graphs. J. ACM 54(6), 27:1\u201327:23 (2007)","DOI":"10.1145\/1314690.1314691"},{"issue":"3-4","key":"9983_CR24","first-page":"260","volume":"17","author":"ME Dyer","year":"2000","unstructured":"Dyer, M. E., Greenhill, C. S.: The complexity of counting graph homomorphisms. Random Struct. Algorithms 17(3-4), 260\u2013289 (2000)","journal-title":"Algorithms"},{"key":"9983_CR25","doi-asserted-by":"crossref","unstructured":"Dyer, M. E., Richerby, D.: On the complexity of #CSP. In: Schulman, L.J. (ed.) Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, pp 725\u2013734. ACM, Cambridge (2010)","DOI":"10.1145\/1806689.1806789"},{"key":"9983_CR26","first-page":"37","volume":"20","author":"M Freedman","year":"2007","unstructured":"Freedman, M., Lov\u00e1sz, L., Schrijver, A.: Reflection positivity, rank connectivity, and homomorphism of graphs. J. AMS 20, 37\u201351 (2007)","journal-title":"J. AMS"},{"issue":"7","key":"9983_CR27","doi-asserted-by":"publisher","first-page":"3336","DOI":"10.1137\/090757496","volume":"39","author":"LA Goldberg","year":"2010","unstructured":"Goldberg, L. A., Grohe, M., Jerrum, M., Thurley, M.: A complexity dichotomy for partition functions with mixed signs. SIAM J. Comput. 39(7), 3336\u20133402 (2010)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"9983_CR28","doi-asserted-by":"publisher","first-page":"25:1","DOI":"10.1145\/2371656.2371660","volume":"59","author":"LA Goldberg","year":"2012","unstructured":"Goldberg, L. A., Jerrum, M.: Approximating the partition function of the ferromagnetic potts model. J. ACM 59(5), 25:1\u201325:31 (2012)","journal-title":"J. ACM"},{"issue":"1","key":"9983_CR29","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P Hell","year":"1990","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the complexity of H-coloring. J. Combin. Theory Ser. B 48(1), 92\u2013110 (1990)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"9983_CR30","first-page":"253","volume":"31","author":"E Ising","year":"1925","unstructured":"Ising, E.: Beitrag zur theorie des ferromagnetismus. Z. Phys. Hadrons Nucl. 31(1), 253\u2013258 (1925)","journal-title":"Z. Phys. Hadrons Nucl."},{"issue":"5","key":"9983_CR31","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1137\/0222066","volume":"22","author":"M Jerrum","year":"1993","unstructured":"Jerrum, M., Sinclair, A.: Polynomial-time approximation algorithms for the ising model. SIAM J. Comput. 22(5), 1087\u20131116 (1993)","journal-title":"SIAM J. Comput."},{"key":"9983_CR32","unstructured":"Jerrum, M., Sinclair, A.: The Markov Chain Monte Carlo Method: an Approach to Approximate Counting and Integration. In: Approximation Algorithms for NP-Hard Problems, pp. 482\u2013520. PWS Publishing (1996)"},{"key":"9983_CR33","doi-asserted-by":"publisher","first-page":"1209","DOI":"10.1016\/0031-8914(61)90063-5","volume":"27","author":"PW Kasteleyn","year":"1961","unstructured":"Kasteleyn, P. W.: The statistics of dimers on a lattice. Physica 27, 1209\u20131225 (1961)","journal-title":"Physica"},{"key":"9983_CR34","unstructured":"Kasteleyn, P. W.: Graph Theory and Crystal Physics. In: Harary, F. (ed.) Graph Theory and Theoretical Physics, pp 43\u2013110. Academic Press, London (1967)"},{"issue":"1","key":"9983_CR35","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"RE Ladner","year":"1975","unstructured":"Ladner, R. E.: On the structure of polynomial time reducibility. J. ACM 22(1), 155\u2013171 (1975)","journal-title":"J. ACM"},{"issue":"3","key":"9983_CR36","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1103\/PhysRev.87.410","volume":"87","author":"T Lee","year":"1952","unstructured":"Lee, T., Yang, C.: Statistical theory of equations of state and phase transitions. II. Lattice gas and Ising model. Phys. Rev. 87(3), 410\u2013419 (1952)","journal-title":"Phys. Rev."},{"issue":"2","key":"9983_CR37","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/BF01213009","volume":"80","author":"E Lieb","year":"1981","unstructured":"Lieb, E., Sokal, A.: A general Lee-Yang theorem for one-component and multicomponent ferromagnets. Commun. Math. Phys. 80(2), 153\u2013179 (1981)","journal-title":"Commun. Math. Phys."},{"key":"9983_CR38","unstructured":"Lin, J., Wang, H.: The Complexity of Holant Problems over Boolean Domain with Non-Negative Weights. In: 44Th International Colloquium on Automata, Languages, and Programming, ICALP 2017, pp 29:1\u201329:14, Warsaw (2017)"},{"key":"9983_CR39","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/BF02280291","volume":"18","author":"L Lov\u00e1sz","year":"1967","unstructured":"Lov\u00e1sz, L.: Operations with structures. Acta Math. Hung. 18, 321\u2013328 (1967)","journal-title":"Acta Math. Hung."},{"issue":"2","key":"9983_CR40","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1214\/aoap\/1026915617","volume":"12","author":"N Madras","year":"2002","unstructured":"Madras, N., Randall, D.: Markov chain decomposition for convergence rate analysis. Ann. Appl. Probab. 12(2), 581\u2013606 (2002)","journal-title":"Ann. Appl. Probab."},{"key":"9983_CR41","doi-asserted-by":"crossref","unstructured":"McCoy, B., Wu, T.: The two-dimensional Ising model. Harvard University Press, Cambridge (1973)","DOI":"10.4159\/harvard.9780674180758"},{"issue":"3-4","key":"9983_CR42","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1103\/PhysRev.65.117","volume":"65","author":"L Onsager","year":"1944","unstructured":"Onsager, L.: Crystal statistics. i. a two-dimensional model with an order-disorder transition. Phys. Rev. 65(3-4), 117\u2013149 (1944)","journal-title":"Phys. Rev."},{"key":"9983_CR43","unstructured":"Randall, D.: Mixing. In: 44Th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings, pp. 4\u201315 (2003)"},{"key":"9983_CR44","doi-asserted-by":"crossref","unstructured":"Schaefer, T. J.: The complexity of satisfiability problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, pp. 216\u2013226, San Diego (1978)","DOI":"10.1145\/800133.804350"},{"key":"9983_CR45","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1090\/S0894-0347-07-00568-1","volume":"20","author":"B Szegedy","year":"2007","unstructured":"Szegedy, B.: Edge coloring models and reflection positivity. J. Amer. Math. Soc. 20, 969\u2013988 (2007)","journal-title":"J. Amer. Math. Soc."},{"key":"9983_CR46","doi-asserted-by":"publisher","first-page":"1061 C 1063","DOI":"10.1080\/14786436108243366","volume":"6","author":"HNV Temperley","year":"1961","unstructured":"Temperley, H. N. V., Fisher, M. E.: Dimer problem in statistical mechanics c an exact result. Philos. Mag. 6, 1061 C 1063 (1961)","journal-title":"Philos. Mag."},{"issue":"4","key":"9983_CR47","doi-asserted-by":"publisher","first-page":"1229","DOI":"10.1137\/S0097539700377025","volume":"31","author":"LG Valiant","year":"2002","unstructured":"Valiant, L. G.: Quantum circuits that can be simulated classically in polynomial time. SIAM J. Comput. 31(4), 1229\u20131254 (2002)","journal-title":"SIAM J. Comput."},{"key":"9983_CR48","doi-asserted-by":"publisher","unstructured":"Valiant, L. G.: Accidental algorthims. In: FOCS \u201906: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science. https:\/\/doi.org\/10.1109\/FOCS.2006.7, pp 509\u2013517. IEEE Computer Society, Washington (2006)","DOI":"10.1109\/FOCS.2006.7"},{"issue":"5","key":"9983_CR49","doi-asserted-by":"publisher","first-page":"1565","DOI":"10.1137\/070682575","volume":"37","author":"LG Valiant","year":"2008","unstructured":"Valiant, L. G.: Holographic algorithms. SIAM J. Comput. 37(5), 1565\u20131594 (2008). https:\/\/doi.org\/10.1137\/070682575","journal-title":"SIAM J. Comput."},{"key":"9983_CR50","doi-asserted-by":"crossref","unstructured":"Welsh, D.: Complexity: knots, colourings and counting. Cambridge University Press, Cambridge (1993)","DOI":"10.1017\/CBO9780511752506"},{"issue":"5","key":"9983_CR51","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1103\/PhysRev.85.808","volume":"85","author":"C Yang","year":"1952","unstructured":"Yang, C.: The spontaneous magnetization of a two-dimensional Ising model. Phys. Rev. 85(5), 808\u2013816 (1952)","journal-title":"Phys. Rev."},{"issue":"3","key":"9983_CR52","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1103\/PhysRev.87.404","volume":"87","author":"C Yang","year":"1952","unstructured":"Yang, C., Lee, T.: Statistical theory of equations of state and phase transitions. I. Theory of condensation. Phys. Rev. 87(3), 404\u2013409 (1952)","journal-title":"Phys. Rev."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09983-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-020-09983-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09983-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,21]],"date-time":"2021-06-21T23:22:15Z","timestamp":1624317735000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-020-09983-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":52,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["9983"],"URL":"https:\/\/doi.org\/10.1007\/s00224-020-09983-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"22 June 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}