{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:18:52Z","timestamp":1725535132931},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642028816"},{"type":"electronic","value":"9783642028823"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-02882-3_47","type":"book-chapter","created":{"date-parts":[[2009,7,10]],"date-time":"2009-07-10T06:49:21Z","timestamp":1247208561000},"page":"472-485","source":"Crossref","is-referenced-by-count":4,"title":["Classification of a Class of Counting Problems Using Holographic Reductions"],"prefix":"10.1007","author":[{"given":"Michael","family":"Kowalczyk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"47_CR1","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A., Dalmau, V.: Towards a Dichotomy Theorem for the Counting Constraint Satisfaction Problem. Information and Computation\u00a0205(5), 651\u2013678 (2007)","DOI":"10.1016\/j.ic.2006.09.005"},{"key":"47_CR2","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A., Grohe, M.: The Complexity of Partition Functions. Theoretical Computer Science\u00a0348(2-3), 148\u2013186 (2005)","DOI":"10.1016\/j.tcs.2005.09.011"},{"key":"47_CR3","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Lu, P.: Holographic Algorithms: From Art to Science. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp. 401\u2013410. ACM Press, New York (2007)","DOI":"10.1145\/1250790.1250850"},{"key":"47_CR4","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Lu, P.: On Symmetric Signatures in Holographic Algorithms. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 429\u2013440. Springer, Heidelberg (2007)","DOI":"10.1007\/978-3-540-70918-3_37"},{"key":"47_CR5","unstructured":"Cai, J.-Y., Chen, X., Lu, P.: Graph Homomorphisms with Complex Values: A Dichotomy Theorem. Computing Research Repository, arXiv:0903.4728v1 (2009)"},{"key":"47_CR6","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Lu, P., Xia, M.: Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 644\u2013653. IEEE Computer Society Press, Los Alamitos (2008)","DOI":"10.1109\/FOCS.2008.34"},{"key":"47_CR7","unstructured":"Cai, J.-Y., Lu, P., Xia, M.: A Computational Approach to Proving Computational Complexity of Some Counting Problems. In: Theory and Applications of Models of Computation: 6th International Conference (to appear, 2009)"},{"key":"47_CR8","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Lu, P., Xia, M.: Holant Problems and Counting CSP. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (to appear, 2009)","DOI":"10.1145\/1536414.1536511"},{"key":"47_CR9","doi-asserted-by":"crossref","unstructured":"Creignou, N., Hermann, M.: Complexity of Generalized Satisfiability Counting Problems. Information and Computation\u00a0125(1), 1\u201312 (1996)","DOI":"10.1006\/inco.1996.0016"},{"key":"47_CR10","doi-asserted-by":"crossref","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classifications of Boolean Constraint Satisfaction Problems. Society for Industrial and Applied Mathematics, Philadelphia (2001)","DOI":"10.1137\/1.9780898718546"},{"key":"47_CR11","doi-asserted-by":"crossref","unstructured":"Dodson, C.T.J., Poston, T.: Tensor Geometry. Springer, New York (1991)","DOI":"10.1007\/978-3-642-10514-2"},{"key":"47_CR12","unstructured":"Dyer, M.E., Goldberg, L.A., Jerrum, M.: The Complexity of Weighted Boolean #CSP. Computing Research Repository, arXiv:0704.3683v2 (2008)"},{"key":"47_CR13","doi-asserted-by":"crossref","unstructured":"Dyer, M.E., Goldberg, L.A., Paterson, M.: On Counting Homomorphisms to Directed Acyclic Graphs. Journal of the ACM\u00a054(6) (2007)","DOI":"10.1145\/1314690.1314691"},{"key":"47_CR14","doi-asserted-by":"crossref","unstructured":"Dyer, M.E., Greenhill, C.S.: The Complexity of Counting Graph Homomorphisms. Random Structures and Algorithms\u00a017(3-4), 260\u2013289 (2000)","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W"},{"key":"47_CR15","doi-asserted-by":"crossref","unstructured":"Freedman, M., Lov\u00e1sz, L., Schrijver, A.: Reflection positivity, rank connectivity, and homomorphism of graphs. Journal of the American Mathematical Society\u00a020, 37\u201351 (2007)","DOI":"10.1090\/S0894-0347-06-00529-7"},{"key":"47_CR16","unstructured":"Goldberg, L.A., Grohe, M., Jerrum, M., Thurley, M.: A complexity dichotomy for partition functions with mixed signs. In: Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (to appear, 2009)"},{"key":"47_CR17","doi-asserted-by":"crossref","unstructured":"Goldberg, L.A., Kelk, S., Paterson, M.: The complexity of choosing an H-colouring (nearly) uniformly at random. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pp. 53\u201362. ACM Press, New York (2002)","DOI":"10.1145\/509907.509917"},{"key":"47_CR18","doi-asserted-by":"crossref","unstructured":"Hell, P., Nes\u0306etr\u0306il, J., Zhu, X.: Duality and polynomial testing of tree homomorphisms. Transactions of the American Mathematical Society\u00a0348(4), 1281\u20131297 (1996)","DOI":"10.1090\/S0002-9947-96-01537-1"},{"key":"47_CR19","doi-asserted-by":"crossref","unstructured":"Kasteleyn, P.W.: The statistics of dimers on a lattice. Physica\u00a027, 1209\u20131225 (1961)","DOI":"10.1016\/0031-8914(61)90063-5"},{"key":"47_CR20","unstructured":"Kasteleyn, P.W.: Graph Theory and Crystal Physics. In: Graph Theory and Theoretical Physics, pp. 43\u2013110. Academic Press, London (1967)"},{"key":"47_CR21","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L.: Operations with structures. Acta Mathematica Academiae Scientiarum Hungaricae\u00a018, 321\u2013328 (1967)","DOI":"10.1007\/BF02280291"},{"key":"47_CR22","doi-asserted-by":"crossref","unstructured":"Temperley, H.N.V., Fisher, M.E.: Dimer problem in statistical mechanics - an exact result. Philosophical Magazine\u00a06, 1061\u20131063 (1961)","DOI":"10.1080\/14786436108243366"},{"key":"47_CR23","doi-asserted-by":"crossref","unstructured":"Vadhan, S.P.: The Complexity of Counting in Sparse, Regular, and Planar Graphs. SIAM Journal on Computing\u00a031(2), 398\u2013427 (2001)","DOI":"10.1137\/S0097539797321602"},{"key":"47_CR24","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: The Complexity of Computing the Permanent. Theoretical Computer Science\u00a08, 189\u2013201 (1979)","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"47_CR25","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Holographic Algorithms (Extended Abstract). In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 306\u2013315. IEEE Computer Society Press, Los Alamitos (2004)","DOI":"10.1109\/FOCS.2004.34"},{"key":"47_CR26","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Quantum Circuits That Can Be Simulated Classically in Polynomial Time. SIAM Journal on Computing\u00a031(4), 1229\u20131254 (2002)","DOI":"10.1137\/S0097539700377025"},{"key":"47_CR27","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Accidental Algorithms. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 509\u2013517. IEEE Computer Society Press, Los Alamitos (2006)","DOI":"10.1109\/FOCS.2006.7"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02882-3_47","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T06:44:59Z","timestamp":1558421099000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02882-3_47"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642028816","9783642028823"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02882-3_47","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}