{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:49:30Z","timestamp":1759063770514},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141645"},{"type":"electronic","value":"9783642141652"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"tdm","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-14165-2_24","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T09:26:02Z","timestamp":1278321962000},"page":"275-286","source":"Crossref","is-referenced-by-count":19,"title":["Graph Homomorphisms with Complex Values: A Dichotomy Theorem"],"prefix":"10.1007","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[]},{"given":"Xi","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"24_CR1","doi-asserted-by":"crossref","unstructured":"Dyer, M., Greenhill, C.: The complexity of counting graph homomorphisms. In: Proceedings of the 9th International Conference on Random Structures and Algorithms, pp. 260\u2013289 (2000)","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.3.CO;2-N"},{"issue":"2","key":"24_CR2","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), 148\u2013186 (2005)","journal-title":"Theoretical Computer Science"},{"key":"24_CR3","unstructured":"Goldberg, L., 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, pp. 493\u2013504 (2009)"},{"key":"24_CR4","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 Mathematica Hungarica\u00a018, 321\u2013328 (1967)","journal-title":"Acta Mathematica Hungarica"},{"key":"24_CR5","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001","volume-title":"Graphs and Homomorphisms","author":"P. Hell","year":"2004","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Graphs and Homomorphisms. Oxford University Press, Oxford (2004)"},{"key":"24_CR6","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1090\/S0894-0347-06-00529-7","volume":"20","author":"M. Freedman","year":"2007","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)","journal-title":"Journal of the American Mathematical Society"},{"issue":"6","key":"24_CR7","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1145\/1314690.1314691","volume":"54","author":"M. Dyer","year":"2007","unstructured":"Dyer, M., Goldberg, L., Paterson, M.: On counting homomorphisms to directed acyclic graphs. Journal of the ACM\u00a054(6) (2007) Article 27","journal-title":"Journal of the ACM"},{"issue":"1","key":"24_CR8","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_CR9","unstructured":"Thurley, M.: The complexity of partition functions on Hermitian matrices. arXiv (1004.0992) (2010)"},{"key":"24_CR10","unstructured":"Cai, J.Y., Chen, X., Lu, P.: Graph homomorphisms with complex values: A dichotomy theorem. arXiv (0903.4728) (2009)"},{"key":"24_CR11","doi-asserted-by":"crossref","unstructured":"Schaefer, T.: The complexity of satisfiability problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"24_CR12","doi-asserted-by":"crossref","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classifications of Boolean Constraint Satisfaction Problems. In: SIAM Monographs on Discrete Mathematics and Applications (2001)","DOI":"10.1137\/1.9780898718546"},{"issue":"1","key":"24_CR13","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1999","unstructured":"Feder, T., Vardi, M.: The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM Journal on Computing\u00a028(1), 57\u2013104 (1999)","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"24_CR14","doi-asserted-by":"publisher","first-page":"1565","DOI":"10.1137\/070682575","volume":"37","author":"L. Valiant","year":"2008","unstructured":"Valiant, L.: Holographic algorithms. SIAM Journal on Computing\u00a037(5), 1565\u20131594 (2008)","journal-title":"SIAM Journal on Computing"},{"key":"24_CR15","doi-asserted-by":"crossref","unstructured":"Valiant, L.: Accidental algorthims. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 509\u2013517 (2006)","DOI":"10.1109\/FOCS.2006.7"},{"key":"24_CR16","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 (2007)","DOI":"10.1145\/1250790.1250850"},{"key":"24_CR17","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, pp. 715\u2013724 (2009)","DOI":"10.1145\/1536414.1536511"},{"key":"24_CR18","volume-title":"The Feynman Lectures on Physics","author":"R. Feynman","year":"1970","unstructured":"Feynman, R., Leighton, R., Sands, M.: The Feynman Lectures on Physics. Addison-Wesley, Reading (1970)"},{"key":"24_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0701-6","volume-title":"Complexity and Real Computation","author":"L. Blum","year":"1998","unstructured":"Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation. Springer, New York (1998)"},{"key":"24_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4684-6802-1","volume-title":"Complexity Theory of Real Functions","author":"K. Ko","year":"1991","unstructured":"Ko, K.: Complexity Theory of Real Functions. Birkh\u00e4user, Boston (1991)"},{"issue":"6","key":"24_CR21","doi-asserted-by":"publisher","first-page":"962","DOI":"10.1016\/j.ejc.2005.04.012","volume":"27","author":"L. Lov\u00e1sz","year":"2006","unstructured":"Lov\u00e1sz, L.: The rank of connection matrices and the dimension of graph algebras. European Journal of Combinatorics\u00a027(6), 962\u2013970 (2006)","journal-title":"European Journal of Combinatorics"},{"key":"24_CR22","series-title":"Encyclopedia of Mathematics and its Applications","volume-title":"Finite Fields.","author":"R. Lidl","year":"1997","unstructured":"Lidl, R., Niederreiter, H.: Finite Fields. . Encyclopedia of Mathematics and its Applications, vol.\u00a020. Cambridge University Press, Cambridge (1997)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T15:41:03Z","timestamp":1558280463000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_24"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}