{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:23:42Z","timestamp":1725557022012},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642135613"},{"type":"electronic","value":"9783642135620"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13562-0_30","type":"book-chapter","created":{"date-parts":[[2010,5,31]],"date-time":"2010-05-31T09:08:30Z","timestamp":1275296910000},"page":"328-339","source":"Crossref","is-referenced-by-count":5,"title":["A Dichotomy for k-Regular Graphs with {0, 1}-Vertex Assignments and Real Edge Functions"],"prefix":"10.1007","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Kowalczyk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2-3","key":"30_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. Theoretical Computer Science\u00a0348(2-3), 148\u2013186 (2005)","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Lu, P., Xia, M.: Holant problems and counting CSP. In: STOC 2009: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pp. 715\u2013724 (2009)","key":"30_CR2","DOI":"10.1145\/1536414.1536511"},{"doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Lu, P.: Holographic algorithms: from art to science. In: STOC 2007: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp. 401\u2013410 (2007)","key":"30_CR3","DOI":"10.1145\/1250790.1250850"},{"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)","key":"30_CR4","DOI":"10.1109\/FOCS.2008.34"},{"key":"30_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1007\/978-3-642-02017-9_17","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)"},{"doi-asserted-by":"crossref","unstructured":"Dyer, M., Goldberg, L.A., Paterson, M.: On counting homomorphisms to directed acyclic graphs. Journal of the ACM\u00a054(6) (2007)","key":"30_CR6","DOI":"10.1145\/1314690.1314691"},{"unstructured":"Dyer, M., Greenhill, C.: The complexity of counting graph homomorphisms (extended abstract). In: SODA 2000: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 246\u2013255 (2000)","key":"30_CR7"},{"unstructured":"Goldberg, L.A., Grohe, M., Jerrum, M., Thurley, M.: A complexity dichotomy for partition functions with mixed signs. CoRR, abs\/0804.1932 (2008)","key":"30_CR8"},{"issue":"1","key":"30_CR9","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"},{"unstructured":"Kowalczyk, M., Cai, J.-Y.: Holant problems for regular graphs with complex edge functions. In: STACS 2010: Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, pp. 525\u2013536 (2010)","key":"30_CR10"},{"key":"30_CR11","doi-asserted-by":"crossref","DOI":"10.1525\/9780520348097","volume-title":"A decision method for elementary algebra and geometry","author":"A. Tarski","year":"1951","unstructured":"Tarski, A.: A decision method for elementary algebra and geometry. University of California Press, Berkeley (1951)"},{"issue":"2","key":"30_CR12","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 Journal on Computing\u00a031(2), 398\u2013427 (2001)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"30_CR13","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 Journal on Computing\u00a08(3), 410\u2013421 (1979)","journal-title":"SIAM Journal on Computing"},{"key":"30_CR14","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. Theoretical Computer Science\u00a08, 189\u2013201 (1979)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"30_CR15","doi-asserted-by":"publisher","first-page":"1229","DOI":"10.1137\/S0097539700377025","volume":"31","author":"L. Valiant","year":"2002","unstructured":"Valiant, L.: Quantum circuits that can be simulated classically in polynomial time. SIAM Journal on Computing\u00a031(4), 1229\u20131254 (2002)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"30_CR16","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. Theoretical Computer Science\u00a0384(1), 111\u2013125 (2007)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13562-0_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T16:45:32Z","timestamp":1635439532000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13562-0_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642135613","9783642135620"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13562-0_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}