{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:25Z","timestamp":1760202625502,"version":"3.40.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,5,9]],"date-time":"2012-05-09T00:00:00Z","timestamp":1336521600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2012,12]]},"DOI":"10.1007\/s00037-012-0044-6","type":"journal-article","created":{"date-parts":[[2012,5,8]],"date-time":"2012-05-08T09:12:50Z","timestamp":1336468370000},"page":"573-604","source":"Crossref","is-referenced-by-count":13,"title":["Holographic reduction, interpolation and hardness"],"prefix":"10.1007","volume":"21","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[]},{"given":"Mingji","family":"Xia","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,5,9]]},"reference":[{"key":"44_CR1","doi-asserted-by":"crossref","unstructured":"Andrei A. Bulatov (2008). The Complexity of the Counting Constraint Satisfaction Problem. In ICALP (1), Luca Aceto, Ivan Damg\u00e5rd, Leslie Ann Goldberg, Magn\u00fas M. Halld\u00f3rsson, Anna Ing\u00f3lfsd\u00f3ttir & Igor Walukiewicz, editors, volume 5125 of Lecture Notes in Computer Science, 646\u2013661. Springer. ISBN 978-3-540-70574-1.","DOI":"10.1007\/978-3-540-70575-8_53"},{"issue":"5","key":"44_CR2","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1016\/j.ic.2006.09.005","volume":"205","author":"Andrei A. Bulatov","year":"2007","unstructured":"Bulatov Andrei A., Victor Dalmau (2007) Towards a dichotomy theorem for the counting constraint satisfaction problem. Information and Computation 205(5): 651\u2013678","journal-title":"Information and Computation"},{"issue":"2-3","key":"44_CR3","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1016\/j.tcs.2005.09.011","volume":"348","author":"Andrei A. Bulatov","year":"2005","unstructured":"Bulatov Andrei A., Martin Grohe (2005) The complexity of partition functions. Theor. Comput. Sci. 348(2-3): 148\u2013186","journal-title":"Theor. Comput. Sci."},{"key":"44_CR4","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai, Xi Chen & Pinyan Lu (2011a). Non-negatively Weighted #CSP: An Effective Complexity Dichotomy. In IEEE Conference on Computational Complexity, 45\u201354. IEEE Computer Society.","DOI":"10.1109\/CCC.2011.32"},{"issue":"1","key":"44_CR5","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.tcs.2007.05.015","volume":"384","author":"Jin-Yi Cai","year":"2007","unstructured":"Cai Jin-Yi, Vinay Choudhary (2007) Valiant\u2019s Holant Theorem and matchgate tensors. Theor. Comput. Sci. 384(1): 22\u201332","journal-title":"Theor. Comput. Sci."},{"key":"44_CR6","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai, Sangxia Huang & Pinyan Lu (2010a). From Holant to #CSP and Back: Dichotomy for Holant c Problems. In ISAAC (1), Otfried Cheong, Kyung-Yong Chwa & Kunsoo Park, editors, volume 6506 of Lecture Notes in Computer Science, 253\u2013265. Springer. ISBN 978-3-642-17516-9.","DOI":"10.1007\/978-3-642-17517-6_24"},{"key":"44_CR7","unstructured":"Jin-Yi Cai & Michael Kowalczyk (2010). A Dichotomy for k-Regular Graphs with {0, 1}-Vertex Assignments and Real Edge Functions. In TAMC, Jan Kratochv\u00edl, Angsheng Li, Jir\u00ed Fiala & Petr Kolman, editors, volume 6108 of Lecture Notes in Computer Science, 328\u2013339. Springer. ISBN 978-3-642-13561-3."},{"key":"44_CR8","unstructured":"Jin-Yi Cai & Michael Kowalczyk (2012). Spin systems on k-regular graphs with complex edge functions. Theoretical Computer Science."},{"issue":"3","key":"44_CR9","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1007\/s00224-009-9229-z","volume":"46","author":"Jin-Yi Cai","year":"2010","unstructured":"Cai Jin-Yi, Pinyan Lu (2010) On Symmetric Signatures in Holographic Algorithms. Theory Comput. Syst. 46(3): 398\u2013415","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"44_CR10","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.jcss.2010.06.005","volume":"77","author":"Jin-Yi Cai","year":"2011","unstructured":"Cai Jin-Yi, Pinyan Lu (2011) Holographic algorithms: From art to science. J. Comput. Syst. Sci. 77(1): 41\u201361","journal-title":"J. Comput. Syst. Sci."},{"key":"44_CR11","unstructured":"Jin-Yi Cai, Pinyan Lu & Mingji Xia (2008). 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, DC, USA."},{"key":"44_CR12","unstructured":"Jin-Yi Cai, Pinyan Lu & Mingji Xia (2009). Holant problems and counting CSP. In STOC, Michael Mitzenmacher, editor, 715\u2013724. ACM. ISBN 978-1-60558-506-2."},{"key":"44_CR13","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai, Pinyan Lu & Mingji Xia (2010b). Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP. In FOCS, 427\u2013436. IEEE Computer Society. ISBN 978-0-7695-4244-7.","DOI":"10.1109\/FOCS.2010.48"},{"issue":"4","key":"44_CR14","doi-asserted-by":"crossref","first-page":"1101","DOI":"10.1137\/100814585","volume":"40","author":"Jin-Yi Cai","year":"2011","unstructured":"Cai Jin-Yi, Pinyan Lu, Xia Mingji (2011) Computational Complexity of Holant Problems. SIAM J. Comput. 40(4): 1101\u20131132","journal-title":"SIAM J. Comput."},{"issue":"23","key":"44_CR15","doi-asserted-by":"crossref","first-page":"2468","DOI":"10.1016\/j.tcs.2010.10.039","volume":"412","author":"Jin-Yi Cai","year":"2011","unstructured":"Cai Jin-Yi, Pinyan Lu, Xia Mingji (2011) A computational proof of complexity of some restricted counting problems. Theor. Comput. Sci. 412(23): 2468\u20132485","journal-title":"Theor. Comput. Sci."},{"key":"44_CR16","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai, Pinyan Lu & Mingji Xia (2011d). Holographic algorithms by Fibonacci gates. Linear Algebra and its Applications.","DOI":"10.1016\/j.laa.2011.02.032"},{"key":"44_CR17","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/0304-3975(92)90234-7","volume":"102","author":"Paul Dagum","year":"1992","unstructured":"Dagum Paul, Michael Luby (1992) Approximating the permanent of graphs with large factors. Theor. Comput. Sci. 102: 283\u2013305","journal-title":"Theor. Comput. Sci."},{"key":"44_CR18","volume-title":"Tensor Geometry. Graduate Texts in Mathematics 130","author":"Christopher T.J. Dodson","year":"1991","unstructured":"Dodson Christopher T.J., Timothy Poston (1991) Tensor Geometry. Graduate Texts in Mathematics 130. Springer-Verlag, New York"},{"key":"44_CR19","unstructured":"Martin E. Dyer, Leslie Ann Goldberg & Mike Paterson (2007). On counting homomorphisms to directed acyclic graphs. J. ACM 54(6)."},{"issue":"3-4","key":"44_CR20","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W","volume":"17","author":"Martin E. Dyer","year":"2000","unstructured":"Dyer Martin E., Greenhill Catherine S. (2000) The complexity of counting graph homomorphisms. Random Struct. Algorithms 17(3-4): 260\u2013289","journal-title":"Random Struct. Algorithms"},{"key":"44_CR21","unstructured":"Martin E. Dyer & David Richerby (2010). On the complexity of #CSP. In Proceedings of the 42nd ACM symposium on Theory of computing, 725\u2013734."},{"issue":"1","key":"44_CR22","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1007\/PL00001601","volume":"9","author":"Catherine S. Greenhill","year":"2000","unstructured":"Greenhill Catherine S. (2000) The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. Computational Complexity 9(1): 52\u201372","journal-title":"Computational Complexity"},{"key":"44_CR23","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF01010403","volume":"48","author":"Mark Jerrum","year":"1987","unstructured":"Jerrum Mark (1987) Two-dimensional monomer-dimer systems are computationally intractable. Journal of Statistical Physics 48: 121\u2013134","journal-title":"Journal of Statistical Physics"},{"key":"44_CR24","doi-asserted-by":"crossref","first-page":"1209","DOI":"10.1016\/0031-8914(61)90063-5","volume":"27","author":"P.W. Kasteleyn","year":"1961","unstructured":"Kasteleyn P.W. (1961) The statistics of dimers on a lattice. Physica 27: 1209\u20131225","journal-title":"Physica"},{"key":"44_CR25","unstructured":"Michael Kowalczyk & Jin-Yi Cai (2010). Holant Problems for Regular Graphs with Complex Edge Functions. In STACS, Jean-Yves Marion & Thomas Schwentick, editors, volume 5 of LIPIcs, 525\u2013536. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. ISBN 978-3-939897-16-3."},{"key":"44_CR26","unstructured":"H. N. V. Temperley & M. E. Fisher (1961). Dimer problem in statistical mechanics C an Exact Result. Philosophical Magazine 6, 1061C 1063."},{"issue":"2","key":"44_CR27","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1137\/S0097539797321602","volume":"31","author":"Salil P. Vadhan","year":"2001","unstructured":"Vadhan Salil P. (2001) The Complexity of Counting in Sparse, Regular, and Planar Graphs. SIAM J. Comput. 31(2): 398\u2013427","journal-title":"SIAM J. Comput."},{"key":"44_CR28","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"Leslie G. Valiant","year":"1979","unstructured":"Valiant Leslie G. (1979) The Complexity of Computing the Permanent. Theor. Comput. Sci. 8: 189\u2013201","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"44_CR29","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"Leslie G. Valiant","year":"1979","unstructured":"Valiant Leslie G. (1979) The Complexity of Enumeration and Reliability Problems. SIAM J. Comput. 8(3): 410\u2013421","journal-title":"SIAM J. Comput."},{"key":"44_CR30","doi-asserted-by":"crossref","unstructured":"Leslie G. Valiant (2006). Accidental Algorithms. In FOCS \u201906: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 509\u2013517. IEEE Computer Society, Washington, DC, USA.","DOI":"10.1109\/FOCS.2006.7"},{"issue":"5","key":"44_CR31","doi-asserted-by":"crossref","first-page":"1565","DOI":"10.1137\/070682575","volume":"37","author":"LeslieG. Valiant","year":"2008","unstructured":"Valiant LeslieG. (2008) Holographic Algorithms. SIAM J. Comput. 37(5): 1565\u20131594","journal-title":"SIAM J. Comput."},{"issue":"1","key":"44_CR32","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/j.tcs.2007.05.023","volume":"384","author":"Mingji Xia","year":"2007","unstructured":"Xia Mingji, Peng Zhang, Zhao Wenbo (2007) Computational complexity of counting problems on 3-regular planar graphs. Theor. Comput. Sci. 384(1): 111\u2013125","journal-title":"Theor. Comput. Sci."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0044-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-012-0044-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0044-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T13:23:54Z","timestamp":1743081834000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-012-0044-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,9]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["44"],"URL":"https:\/\/doi.org\/10.1007\/s00037-012-0044-6","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2012,5,9]]}}}