{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:17:32Z","timestamp":1760203052898},"publisher-location":"Berlin, Heidelberg","reference-count":44,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_23","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"271-282","source":"Crossref","is-referenced-by-count":0,"title":["Holographic Algorithms Beyond Matchgates"],"prefix":"10.1007","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[]},{"given":"Heng","family":"Guo","sequence":"additional","affiliation":[]},{"given":"Tyson","family":"Williams","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"38-40","key":"23_CR1","doi-asserted-by":"publisher","first-page":"3949","DOI":"10.1016\/j.tcs.2009.06.003","volume":"410","author":"A. Bulatov","year":"2009","unstructured":"Bulatov, A., Dyer, M., Goldberg, L.A., Jalsenius, M., Richerby, D.: The complexity of weighted Boolean #CSP with mixed signs. Theor. Comput. Sci.\u00a0410(38-40), 3949\u20133961 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"23_CR2","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/j.tcs.2005.09.011","volume":"348","author":"A. Bulatov","year":"2005","unstructured":"Bulatov, A., Grohe, M.: The complexity of partition functions. Theor. Comput. Sci.\u00a0348(2), 148\u2013186 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"23_CR3","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A.: The complexity of the counting constraint satisfaction problem. J. ACM\u00a060(5), 34:1\u201334:41 (2013)","DOI":"10.1145\/2528400"},{"issue":"5","key":"23_CR4","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1016\/j.ic.2006.09.005","volume":"205","author":"A.A. Bulatov","year":"2007","unstructured":"Bulatov, A.A., Dalmau, V.: Towards a dichotomy theorem for the counting constraint satisfaction problem. Inform. and Comput.\u00a0205(5), 651\u2013678 (2007)","journal-title":"Inform. and Comput."},{"key":"23_CR5","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Chen, X.: A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights. In: FOCS, pp. 437\u2013446. IEEE Computer Society (2010)","DOI":"10.1109\/FOCS.2010.49"},{"key":"23_CR6","unstructured":"Cai, J.-Y., Chen, X.: Complexity of counting CSP with complex weights. In: STOC, pp. 909\u2013920. ACM (2012), arXiv:1111.2384"},{"key":"23_CR7","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Chen, X., Lu, P.: Non-negatively weighted #CSP: An effective complexity dichotomy. In: IEEE Conference on Computational Complexity, pp. 45\u201354. IEEE Computer Society (2011)","DOI":"10.1109\/CCC.2011.32"},{"issue":"3","key":"23_CR8","doi-asserted-by":"publisher","first-page":"924","DOI":"10.1137\/110840194","volume":"42","author":"J.-Y. Cai","year":"2013","unstructured":"Cai, J.-Y., Chen, X., Lu, P.: Graph homomorphisms with complex values: A dichotomy theorem. SIAM J. Comput.\u00a042(3), 924\u20131029 (2013)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"23_CR9","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/s00224-007-9092-8","volume":"45","author":"J.-Y. Cai","year":"2009","unstructured":"Cai, J.-Y., Choudhary, V., Lu, P.: On the theory of matchgate computations. Theory of Computing Systems\u00a045(1), 108\u2013132 (2009)","journal-title":"Theory of Computing Systems"},{"issue":"868","key":"23_CR10","first-page":"4001","volume":"10","author":"J.-Y. Cai","year":"2014","unstructured":"Cai, J.-Y., Gorenstein, A.: Matchgates revisited. Theory of Computing\u00a010(868), 4001\u20134030 (2014)","journal-title":"Theory of Computing"},{"key":"23_CR11","unstructured":"Cai, J.-Y., Guo, H., Williams, T.: A complete dichotomy rises from the capture of vanishing signatures (extended abstract). In: STOC, pp. 635\u2013644. ACM (2013), arXiv:1204.6445"},{"key":"23_CR12","unstructured":"Cai, J.-Y., Guo, H., Williams, T.: Holographic algorithms beyond matchgates. CoRR, abs\/1307.7430 (2013)"},{"issue":"3","key":"23_CR13","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/s00453-012-9626-6","volume":"64","author":"J.-Y. Cai","year":"2012","unstructured":"Cai, J.-Y., Huang, S., Lu, P.: From Holant to #CSP and back: Dichotomy for Holant\n                    c\n                   problems. Algorithmica\u00a064(3), 511\u2013533 (2012)","journal-title":"Algorithmica"},{"key":"23_CR14","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2012.01.021","volume":"461","author":"J.-Y. Cai","year":"2012","unstructured":"Cai, J.-Y., Kowalczyk, M.: Spin systems on k-regular graphs with complex edge functions. Theor. Comput. Sci.\u00a0461, 2\u201316 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"23_CR15","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Kowalczyk, M., Williams, T.: Gadgets and anti-gadgets leading to a complexity dichotomy. In: ITCS, pp. 452\u2013467. ACM (2012)","DOI":"10.1145\/2090236.2090272"},{"key":"23_CR16","unstructured":"Cai, J.-Y., Lu, P.: Holographic algorithms with unsymmetric signatures. In: SODA, pp. 54\u201363. Society for Industrial and Applied Mathematics (2008)"},{"issue":"1","key":"23_CR17","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.jcss.2010.06.005","volume":"77","author":"J.-Y. Cai","year":"2011","unstructured":"Cai, J.-Y., Lu, P.: Holographic algorithms: From art to science. J. Comput. Syst. Sci.\u00a077(1), 41\u201361 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"23_CR18","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1007\/s00453-009-9383-3","volume":"61","author":"J.-Y. Cai","year":"2011","unstructured":"Cai, J.-Y., Lu, P.: Signature theory in holographic algorithms. Algorithmica\u00a061(4), 779\u2013816 (2011)","journal-title":"Algorithmica"},{"key":"23_CR19","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Lu, P., Xia, M.: Holographic algorithms with matchgates capture precisely tractable planar #CSP. In: FOCS, pp. 427\u2013436. IEEE Computer Society (2010)","DOI":"10.1109\/FOCS.2010.48"},{"issue":"4","key":"23_CR20","doi-asserted-by":"publisher","first-page":"1101","DOI":"10.1137\/100814585","volume":"40","author":"J.-Y. Cai","year":"2011","unstructured":"Cai, J.-Y., Lu, P., Xia, M.: Computational complexity of Holant problems. SIAM J. Comput.\u00a040(4), 1101\u20131132 (2011)","journal-title":"SIAM J. Comput."},{"key":"23_CR21","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Lu, P., Xia, M.: Dichotomy for Holant* problems of Boolean domain. In: SODA, pp. 1714\u20131728. SIAM (2011)","DOI":"10.1137\/1.9781611973082.132"},{"issue":"4","key":"23_CR22","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1007\/s00037-012-0044-6","volume":"21","author":"J.-Y. Cai","year":"2012","unstructured":"Cai, J.-Y., Lu, P., Xia, M.: Holographic reduction, interpolation and hardness. Computational Complexity\u00a021(4), 573\u2013604 (2012)","journal-title":"Computational Complexity"},{"key":"23_CR23","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Lu, P., Xia, M.: Dichotomy for Holant* problems with domain size 3. In: SODA, pp. 1278\u20131295. SIAM (2013)","DOI":"10.1137\/1.9781611973105.93"},{"issue":"2","key":"23_CR24","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1016\/j.laa.2011.02.032","volume":"438","author":"J.-Y. Cai","year":"2013","unstructured":"Cai, J.-Y., Lu, P., Xia, M.: Holographic algorithms by Fibonacci gates. Linear Algebra and its Applications\u00a0438(2), 690\u2013707 (2013)","journal-title":"Linear Algebra and its Applications"},{"issue":"1","key":"23_CR25","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/j.jcss.2013.07.003","volume":"80","author":"J.-Y. Cai","year":"2014","unstructured":"Cai, J.-Y., Lu, P., Xia, M.: The complexity of complex weighted Boolean #CSP. J. Comput. System Sci.\u00a080(1), 217\u2013236 (2014)","journal-title":"J. Comput. System Sci."},{"issue":"5","key":"23_CR26","doi-asserted-by":"publisher","first-page":"1970","DOI":"10.1137\/070690201","volume":"38","author":"M. Dyer","year":"2009","unstructured":"Dyer, M., Goldberg, L.A., Jerrum, M.: The complexity of weighted Boolean #CSP. SIAM J. Comput.\u00a038(5), 1970\u20131986 (2009)","journal-title":"SIAM J. Comput."},{"key":"23_CR27","doi-asserted-by":"crossref","unstructured":"Dyer, M., Goldberg, L.A., Paterson, M.: On counting homomorphisms to directed acyclic graphs. J. ACM\u00a054(6) (2007)","DOI":"10.1145\/1314690.1314691"},{"issue":"3-4","key":"23_CR28","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W","volume":"17","author":"M. Dyer","year":"2000","unstructured":"Dyer, M., Greenhill, C.: The complexity of counting graph homomorphisms. Random Struct. Algorithms\u00a017(3-4), 260\u2013289 (2000)","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"23_CR29","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1137\/100811258","volume":"42","author":"M. Dyer","year":"2013","unstructured":"Dyer, M., Richerby, D.: An effective dichotomy for the counting constraint satisfaction problem. SIAM J. Comput.\u00a042(3), 1245\u20131274 (2013)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"23_CR30","doi-asserted-by":"publisher","first-page":"3336","DOI":"10.1137\/090757496","volume":"39","author":"L.A. 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.\u00a039(7), 3336\u20133402 (2010)","journal-title":"SIAM J. Comput."},{"key":"23_CR31","unstructured":"Guo, H., Huang, S., Lu, P., Xia, M.: The complexity of weighted Boolean #CSP modulo\u00a0k. In: STACS, pp. 249\u2013260. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2011)"},{"key":"23_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1007\/978-3-642-39206-1_44","volume-title":"Automata, Languages, and Programming","author":"H. Guo","year":"2013","unstructured":"Guo, H., Williams, T.: The complexity of planar Boolean #CSP with complex weights. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol.\u00a07965, pp. 516\u2013527. Springer, Heidelberg (2013)"},{"issue":"1","key":"23_CR33","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. Comb. Theory Ser. B\u00a048(1), 92\u2013110 (1990)","journal-title":"J. Comb. Theory Ser. B"},{"key":"23_CR34","doi-asserted-by":"crossref","unstructured":"Huang, S., Lu, P.: A dichotomy for real weighted Holant problems. In: IEEE Conference on Computational Complexity, pp. 96\u2013106. IEEE Computer Society (2012)","DOI":"10.1109\/CCC.2012.16"},{"issue":"12","key":"23_CR35","doi-asserted-by":"publisher","first-page":"1209","DOI":"10.1016\/0031-8914(61)90063-5","volume":"27","author":"P.W. Kasteleyn","year":"1961","unstructured":"Kasteleyn, P.W.: The statistics of dimers on a lattice. Physica\u00a027(12), 1209\u20131225 (1961)","journal-title":"Physica"},{"key":"23_CR36","first-page":"43","volume-title":"Graph Theory and Theoretical Physics","author":"P.W. Kasteleyn","year":"1967","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)"},{"key":"23_CR37","doi-asserted-by":"crossref","unstructured":"Kayal, N.: Affine projections of polynomials: Extended abstract. In: STOC, pp. 643\u2013662. ACM (2012)","DOI":"10.1145\/2213977.2214036"},{"issue":"3-4","key":"23_CR38","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.\u00a018(3-4), 321\u2013328 (1967)","journal-title":"Acta Math. Hung."},{"issue":"2","key":"23_CR39","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1137\/S009753970038715X","volume":"31","author":"K.D. Mulmuley","year":"2001","unstructured":"Mulmuley, K.D., Sohoni, M.: Geometric complexity theory I: An approach to the P vs. NP and related problems. SIAM J. Comput.\u00a031(2), 496\u2013526 (2001)","journal-title":"SIAM J. Comput."},{"issue":"68","key":"23_CR40","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1080\/14786436108243366","volume":"6","author":"H.N.V. Temperley","year":"1961","unstructured":"Temperley, H.N.V.: Michael\u00a0E. Fisher. Dimer problem in statistical mechanics\u2014an exact result. Philosophical Magazine\u00a06(68), 1061\u20131063 (1961)","journal-title":"Philosophical Magazine"},{"issue":"1","key":"23_CR41","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1016\/S0304-3975(01)00325-5","volume":"289","author":"L.G. Valiant","year":"2002","unstructured":"Valiant, L.G.: Expressiveness of matchgates. Theor. Comput. Sci.\u00a0289(1), 457\u2013471 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"23_CR42","doi-asserted-by":"publisher","first-page":"1229","DOI":"10.1137\/S0097539700377025","volume":"31","author":"L.G. Valiant","year":"2002","unstructured":"Valiant, L.G.: Quantum circuits that can be simulated classically in polynomial time. SIAM J. Comput.\u00a031(4), 1229\u20131254 (2002)","journal-title":"SIAM J. Comput."},{"key":"23_CR43","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Accidental algorthims. In: FOCS, pp. 509\u2013517. IEEE Computer Society (2006)","DOI":"10.1109\/FOCS.2006.7"},{"issue":"5","key":"23_CR44","doi-asserted-by":"publisher","first-page":"1565","DOI":"10.1137\/070682575","volume":"37","author":"L.G. Valiant","year":"2008","unstructured":"Valiant, L.G.: Holographic algorithms. SIAM J. Comput.\u00a037(5), 1565\u20131594 (2008)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T02:27:15Z","timestamp":1558924035000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":44,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}