{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:33:06Z","timestamp":1787340786187,"version":"build-2736575974"},"reference-count":49,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"name":"China National 973 Program","award":["2014CB340300"],"award-info":[{"award-number":["2014CB340300"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61003030"],"award-info":[{"award-number":["61003030"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0511679"],"award-info":[{"award-number":["CCF-0511679"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0830488"],"award-info":[{"award-number":["CCF-0830488"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0914969"],"award-info":[{"award-number":["CCF-0914969"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1217549"],"award-info":[{"award-number":["CCF-1217549"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>Valiant introduced matchgate computation and holographic algorithms. A number of seemingly exponential time problems can be solved by this novel algorithmic paradigm in polynomial time. We show that, in a very strong sense, matchgate computations and holographic algorithms based on them provide a universal methodology to a broad class of counting problems studied in the statistical physics community for decades. They capture precisely those problems which are #P-hard on general graphs but computable in polynomial time on planar graphs. More precisely, we prove complexity dichotomy theorems in the framework of counting CSP problems. The local constraint functions take Boolean inputs and can be arbitrary real-valued symmetric functions. We prove that every problem in this class belongs to precisely three categories: (1) those which are tractable (i.e., polynomial time computable) on general graphs, or (2) those which are #P-hard on general graphs but tractable on planar graphs, or (3) those which are #P-hard even on planar graphs. The classification criteria are explicit. Moreover, problems in category (2) are tractable on planar graphs precisely by holographic algorithms with matchgates.<\/jats:p>","DOI":"10.1137\/16m1073984","type":"journal-article","created":{"date-parts":[[2017,5,11]],"date-time":"2017-05-11T11:14:56Z","timestamp":1494501296000},"page":"853-889","source":"Crossref","is-referenced-by-count":16,"title":["Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP"],"prefix":"10.1137","volume":"46","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mingji","family":"Xia","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,5,11]]},"reference":[{"key":"atypb1","unstructured":"R. J. Baxter,\n                      Exactly Solved Models in Statistical Mechanics\n                      , Academic Press, London, 1982."},{"key":"atypb2","first-page":"646","author":"Bulatov A. A.","year":"2008","journal-title":"New York"},{"key":"atypb3","first-page":"562","author":"Bulatov A. A.","year":"2003","journal-title":"Proceedings of FOCS, IEEE"},{"key":"atypb4","first-page":"294","author":"Bulatov A. A.","year":"2004","journal-title":"New York"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.011"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/110840194"},{"key":"atypb7","first-page":"703","author":"Cai J.-Y.","year":"2006","journal-title":"New York"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.05.015"},{"key":"atypb9","first-page":"305","author":"Cai J.-Y.","year":"2007","journal-title":"Washington, DC"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2014.v010a007"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"J.Y. Cai, H. Guo, and T. Williams,\n                      A complete dichotomy rises from the capture of vanishing signatures: Extended abstract\n                      , in Proceedings of the Symposium on Theory of Computing Conference, Palo Alto, CA, 2013, pp. 635-644.","DOI":"10.1145\/2488608.2488687"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9626-6"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"J.Y. Cai, P. Lu, and M. Xia,\n                      Holographic algorithms with matchgates capture precisely tractable planar_#CSP\n                      , in Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010, pp. 427-436.","DOI":"10.1109\/FOCS.2010.48"},{"key":"atypb14","first-page":"401","author":"Cai J.-Y.","year":"2007","journal-title":"ACM"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-008-0249-x"},{"key":"atypb16","first-page":"54","author":"Cai J.-Y.","year":"2008","journal-title":"Philadelphia"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9229-z"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"J.Y. Cai, P. Lu, and M. Xia,\n                      Holographic algorithms by fibonacci gates and holographic reductions for hardness\n                      , in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, Washington, DC, IEEE, 2008.","DOI":"10.1109\/FOCS.2008.34"},{"key":"atypb19","first-page":"138","author":"Cai J.-Y.","year":"2009","journal-title":"New York"},{"key":"atypb20","first-page":"715","author":"Cai J.-Y.","year":"2009","journal-title":"New York"},{"key":"atypb21","first-page":"33","author":"Cipra B. A.","year":"2000","journal-title":"SIAM News"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"C. T. J. Dodson and T. Poston,\n                      Tensor Geometry\n                      , Grad. Texts in Math. 130, Springer-Verlag, New York, 1991.","DOI":"10.1007\/978-3-642-10514-2"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1145\/1314690.1314691"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W"},{"key":"atypb25","first-page":"37","volume":"20","author":"Freedman M.","year":"2007","journal-title":"J. AMS"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/100815530"},{"key":"atypb27","first-page":"253","volume":"31","author":"Ising E.","year":"1925","journal-title":"Z. Phys. A Hadrons Nuclei"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335316"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1016\/0031-8914(61)90063-5"},{"key":"atypb30","first-page":"43","author":"Kasteleyn P. W.","year":"1967","journal-title":"London"},{"key":"atypb31","first-page":"472","author":"Kowalczyk M.","year":"2009","journal-title":"New York"},{"key":"atypb32","first-page":"525","author":"Kowalczyk M.","year":"2010","journal-title":"Proceeding of STACS"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.87.410"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1007\/BF01213009"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"B. M. McCoy and T. T. Wu,\n                      The Two-Dimensional Ising Model\n                      , Harvard University Press, Cambridge, MA, 1973.","DOI":"10.4159\/harvard.9780674180758"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.65.117"},{"key":"atypb37","unstructured":"L. Onsager,\n                      Discussion\n                      , Nuovo Cimento (suppl.), 2 (1949), p. 261."},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1080\/14786436108243366"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797321602"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00325-5"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700377025"},{"key":"atypb44","first-page":"509","author":"Valiant L. G.","year":"2006","journal-title":"Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, Washington, DC"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1137\/070682575"},{"key":"atypb46","doi-asserted-by":"crossref","unstructured":"D. Welsh,\n                      Complexity: Knots, Colourings and Counting\n                      , Cambridge University Press, Cambridge, UK, 1993.","DOI":"10.1017\/CBO9780511752506"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.05.023"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.85.808"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.87.404"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1073984","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:47:57Z","timestamp":1787338077000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1073984"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/16M1073984"],"URL":"https:\/\/doi.org\/10.1137\/16m1073984","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}