{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:55:39Z","timestamp":1725558939951},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141645"},{"type":"electronic","value":"9783642141652"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_56","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T13:26:02Z","timestamp":1278336362000},"page":"666-677","source":"Crossref","is-referenced-by-count":2,"title":["Holographic Reduction: A Domain Changed Application and Its Partial Converse Theorems"],"prefix":"10.1007","author":[{"given":"Mingji","family":"Xia","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"2-3","key":"56_CR1","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-3), 148\u2013186 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"56_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"646","DOI":"10.1007\/978-3-540-70575-8_53","volume-title":"Automata, Languages and Programming","author":"A. Bulatov","year":"2008","unstructured":"Bulatov, A.: The complexity of the counting constraint satisfaction problem. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 646\u2013661. Springer, Heidelberg (2008)"},{"issue":"38-40","key":"56_CR3","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., 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":"1","key":"56_CR4","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.tcs.2007.05.015","volume":"384","author":"J.-Y. Cai","year":"2007","unstructured":"Cai, J.-Y., Choudhary, V.: Valiant\u2019s holant theorem and matchgate tensors. Theor. Comput. Sci.\u00a0384(1), 22\u201332 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"18","key":"56_CR5","doi-asserted-by":"publisher","first-page":"1618","DOI":"10.1016\/j.tcs.2008.12.047","volume":"410","author":"J.-Y. Cai","year":"2009","unstructured":"Cai, J.-Y., Lu, P.: Holographic algorithms: The power of dimensionality resolved. Theor. Comput. Sci.\u00a0410(18), 1618\u20131628 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"4-5","key":"56_CR6","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1016\/j.tcs.2009.10.012","volume":"411","author":"J.-Y. Cai","year":"2010","unstructured":"Cai, J.-Y., Lu, P.: On blockwise symmetric signatures for matchgates. Theor. Comput. Sci.\u00a0411(4-5), 739\u2013750 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"56_CR7","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Lu, P.: Holographic algorithms: from art to science. In: STOC 2007, pp. 401\u2013410 (2007)","DOI":"10.1145\/1250790.1250850"},{"key":"56_CR8","unstructured":"Cai, J.-Y., Chen, X., Lu, P.: Graph homomorphisms with complex values: a dichotomy theorem. CoRR abs\/0903.4728 (2009)"},{"key":"56_CR9","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Lu, P., Xia, M.: Holographic algorithms by Fibonacci gates and holographic reductions for hardness. In: FOCS 2008, pp. 644\u2013653 (2008)","DOI":"10.1109\/FOCS.2008.34"},{"key":"56_CR10","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Lu, P., Xia, M.: Holant problems and counting CSP. In: STOC 2009, pp. 715\u2013724 (2009)","DOI":"10.1145\/1536414.1536511"},{"key":"56_CR11","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Lu, P., Xia, M.: A computational proof of complexity of some restricted counting problems. In: TAMC 2009, pp. 138\u2013149 (2009)","DOI":"10.1007\/978-3-642-02017-9_17"},{"issue":"1","key":"56_CR12","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.\u00a0125(1), 1\u201312 (1996)","journal-title":"Inf. Comput."},{"key":"56_CR13","doi-asserted-by":"crossref","unstructured":"Dyer, M., Goldberg, L., Paterson, M.: On counting homomorphisms to directed acyclic graphs. J. ACM\u00a054(6) (2007)","DOI":"10.1145\/1314690.1314691"},{"issue":"5","key":"56_CR14","doi-asserted-by":"publisher","first-page":"1970","DOI":"10.1137\/070690201","volume":"38","author":"M. Dyer","year":"2009","unstructured":"Dyer, M., Goldberg, L., Jerrum, M.: The complexity of weighted Boolean CSP. SIAM J. Comput.\u00a038(5), 1970\u20131986 (2009)","journal-title":"SIAM J. Comput."},{"key":"56_CR15","unstructured":"Dyer, M., Goldberg, L., Jerrum, M.: A complexity dichotomy for hypergraph partition functions. CoRR abs\/0811.0037 (2008)"},{"issue":"3-4","key":"56_CR16","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"},{"key":"56_CR17","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. Acad. Sci. Hung.\u00a018, 321\u2013328 (1967)","journal-title":"Acta Math. Acad. Sci. Hung."},{"issue":"2","key":"56_CR18","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1137\/S0097539797321602","volume":"31","author":"S. Vadhan","year":"2001","unstructured":"Vadhan, S.: The complexity of counting in sparse, regular, and planar graphs. SIAM J. Comput.\u00a031(2), 398\u2013427 (2001)","journal-title":"SIAM J. Comput."},{"key":"56_CR19","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. Valiant","year":"1979","unstructured":"Valiant, L.: The complexity of computing the permanent. Theor. Comput. Sci.\u00a08, 189\u2013201 (1979)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"56_CR20","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L. Valiant","year":"1979","unstructured":"Valiant, L.: The complexity of enumeration and reliability problems. SIAM J. Comput.\u00a08(3), 410\u2013421 (1979)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"56_CR21","doi-asserted-by":"publisher","first-page":"1565","DOI":"10.1137\/070682575","volume":"37","author":"L. Valiant","year":"2008","unstructured":"Valiant, L.: Holographic algorithms. SIAM J. Comput.\u00a037(5), 1565\u20131594 (2008)","journal-title":"SIAM J. Comput."},{"key":"56_CR22","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Automata, Languages and Programming","author":"L. Valiant","year":"2005","unstructured":"Valiant, L.: Holographic circuits. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1\u201315. Springer, Heidelberg (2005)"},{"key":"56_CR23","doi-asserted-by":"crossref","unstructured":"Valiant, L.: Accidental algorthims. In: FOCS 2006, pp. 509\u2013517 (2006)","DOI":"10.1109\/FOCS.2006.7"},{"issue":"1","key":"56_CR24","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.tcs.2007.05.023","volume":"384","author":"M. Xia","year":"2007","unstructured":"Xia, M., Zhang, P., Zhao, W.: Computational complexity of counting problems on 3-regular planar graphs. Theor. Comput. Sci.\u00a0384(1), 111\u2013125 (2007)","journal-title":"Theor. Comput. Sci."}],"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-642-14165-2_56.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T12:20:35Z","timestamp":1619785235000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_56"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_56","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}