{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T21:07:33Z","timestamp":1725570453403},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642175169"},{"type":"electronic","value":"9783642175176"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-17517-6_24","type":"book-chapter","created":{"date-parts":[[2010,12,3]],"date-time":"2010-12-03T15:13:41Z","timestamp":1291389221000},"page":"253-265","source":"Crossref","is-referenced-by-count":4,"title":["From Holant to #CSP and Back: Dichotomy for Holant c Problems"],"prefix":"10.1007","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[]},{"given":"Sangxia","family":"Huang","sequence":"additional","affiliation":[]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"24_CR1","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/1120582.1120584","volume":"53","author":"A. Bulatov","year":"2006","unstructured":"Bulatov, A.: A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM\u00a053(1), 66\u2013120 (2006)","journal-title":"J. ACM"},{"key":"24_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":"5","key":"24_CR3","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1016\/j.ic.2006.09.005","volume":"205","author":"A. Bulatov","year":"2007","unstructured":"Bulatov, A., Dalmau, V.: Towards a dichotomy theorem for the counting constraint satisfaction problem. Inf. Comput.\u00a0205(5), 651\u2013678 (2007)","journal-title":"Inf. Comput."},{"issue":"2-3","key":"24_CR4","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":"24_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/978-3-642-14165-2_24","volume-title":"ICALP 2010","author":"J.-Y. Cai","year":"2010","unstructured":"Cai, J.-Y., Chen, X., Lu, P.: Graph homomorphisms with complex values: A dichotomy theorem. In: Gavoille, C. (ed.) ICALP 2010, Part I. LNCS, vol.\u00a06198, pp. 275\u2013286. Springer, Heidelberg (2010)"},{"key":"24_CR6","unstructured":"Cai, J.-Y., Huang, S., Lu, P.: From Holant To #CSP And Back: Dichotomy For Holantc Problems. CoRR, abs\/1004.0803 (2010), http:\/\/arxiv.org\/abs\/1004.0803"},{"key":"24_CR7","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Lu, P.: Holographic algorithms: from art to science. In: STOC 2007: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, pp. 401\u2013410 (2007)","DOI":"10.1145\/1250790.1250850"},{"key":"24_CR8","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: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 644\u2013653 (2008)","DOI":"10.1109\/FOCS.2008.34"},{"key":"24_CR9","series-title":"LNCS","first-page":"138","volume-title":"TAMC 2009","author":"J.-Y. Cai","year":"2009","unstructured":"Cai, J.-Y., Lu, P., Xia, M.: A Computational Proof of Complexity of Some Restricted Counting Problems. In: Chen, J., Cooper, S.B. (eds.) TAMC 2009. LNCS, vol.\u00a05532, pp. 138\u2013149. Springer, Heidelberg (2009)"},{"key":"24_CR10","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Lu, P., Xia, M.: Holant Problems and Counting CSP. In: STOC 2009: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of computing, pp. 715\u2013724 (2009)","DOI":"10.1145\/1536414.1536511"},{"key":"24_CR11","series-title":"Monographs on Discrete Mathematics and Applications","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718546","volume-title":"Complexity classifications of boolean constraint satisfaction problems","author":"N. Creignou","year":"2001","unstructured":"Creignou, N., Khanna, N., Sudan, M.: Complexity classifications of boolean constraint satisfaction problems. SIAM Monographs on Discrete Mathematics and Applications (2001)"},{"key":"24_CR12","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/0304-3975(92)90234-7","volume":"102","author":"P. Dagum","year":"1992","unstructured":"Dagum, P., Luby, M.: Approximating the permanent of graphs with large factors. Theor. Comput. Sci.\u00a0102, 283\u2013305 (1992)","journal-title":"Theor. Comput. Sci."},{"key":"24_CR13","unstructured":"Dyer, M.E., Goldberg, L.A., Jerrum, M.: The complexity of weighted boolean #CSP. CoRR, abs\/0704.3683 (2007)"},{"key":"24_CR14","doi-asserted-by":"crossref","unstructured":"Dyer, M.E., Goldberg, L.A., Paterson, M.: On counting homomorphisms to directed acyclic graphs. J. ACM\u00a054(6) (2007)","DOI":"10.1145\/1314690.1314691"},{"key":"24_CR15","unstructured":"Dyer, M.E., Greenhill, C.S.: The complexity of counting graph homomorphisms (extended abstract). In: Proceedings of SODA, pp. 246\u2013255 (2000)"},{"issue":"3","key":"24_CR16","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1002\/rsa.20036","volume":"25","author":"M.E. Dyer","year":"2004","unstructured":"Dyer, M.E., Greenhill, C.S.: Corrigendum: The complexity of counting graph homomorphisms. Random Struct. Algorithms\u00a025(3), 346\u2013352 (2004)","journal-title":"Random Struct. Algorithms"},{"issue":"1","key":"24_CR17","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1998","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic snp and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput.\u00a028(1), 57\u2013104 (1998)","journal-title":"SIAM J. Comput."},{"key":"24_CR18","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\u00a020, 37\u201351 (2007)","journal-title":"J. AMS"},{"key":"24_CR19","unstructured":"Goldberg, L.A., Grohe, M., Jerrum, M., Thurley, M.: A complexity dichotomy for partition functions with mixed signs. In: Proceedings of STACS, pp. 493\u2013504 (2009), CoRR, abs\/0804.1932 (2008)"},{"issue":"1","key":"24_CR20","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. Journal of Combinatorial Theory, Series B\u00a048(1), 92\u2013110 (1990)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"24_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1007\/978-3-642-02882-3_47","volume-title":"Computing and Combinatorics","author":"M. Kowalczyk","year":"2009","unstructured":"Kowalczyk, M.: Classification of a Class of Counting Problems Using Holographic Reductions. In: Ngo, H.Q. (ed.) COCOON 2009. LNCS, vol.\u00a05609, pp. 472\u2013485. Springer, Heidelberg (2009)"},{"key":"24_CR22","unstructured":"Kowalczyk, M., Cai, J.-Y.: Holant Problems for Regular Graphs with Complex Edge Functions. In: Proceedings of STACS, pp. 525\u2013536 (2010)"},{"issue":"2","key":"24_CR23","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1137\/S0097539797321602","volume":"31","author":"S.P. Vadhan","year":"2001","unstructured":"Vadhan, S.P.: The complexity of counting in sparse, regular, and planar graphs. SIAM J. Comput.\u00a031(2), 398\u2013427 (2001)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"24_CR24","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput.\u00a08(3), 410\u2013421 (1979)","journal-title":"SIAM J. Comput."},{"key":"#cr-split#-24_CR25.1","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Holographic algorithms. In: FOCS 2004: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 306???315 (2004);","DOI":"10.1109\/FOCS.2004.34"},{"key":"#cr-split#-24_CR25.2","doi-asserted-by":"crossref","unstructured":"SIAM J. Comput. 37(5), 1565???1594 (2008)","DOI":"10.1137\/070682575"},{"key":"24_CR26","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Accidental algorthims. In: FOCS 2006: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 509\u2013517 (2006)","DOI":"10.1109\/FOCS.2006.7"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-17517-6_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T15:49:24Z","timestamp":1559836164000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17517-6_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642175169","9783642175176"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17517-6_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}