{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,3]],"date-time":"2025-10-03T17:51:45Z","timestamp":1759513905450},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,5,10]],"date-time":"2016-05-10T00:00:00Z","timestamp":1462838400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2017,8]]},"DOI":"10.1007\/s00493-016-3357-2","type":"journal-article","created":{"date-parts":[[2016,5,9]],"date-time":"2016-05-09T21:43:18Z","timestamp":1462830198000},"page":"633-650","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Computing the partition function for graph homomorphisms"],"prefix":"10.1007","volume":"37","author":[{"given":"Alexander","family":"Barvinok","sequence":"first","affiliation":[]},{"given":"Pablo","family":"Sober\u00f3n","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,5,10]]},"reference":[{"key":"3357_CR1","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1023\/A:1008647514949","volume":"8","author":"N. Alon","year":"1998","unstructured":"N. Alon and T.H. Marshall: Homomorphisms of edge-colored graphs and Coxeter groups, Journal of Algebraic Combinatorics\n8 (1998), 5\u201313.","journal-title":"Journal of Algebraic Combinatorics"},{"key":"3357_CR2","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/s10208-014-9243-7","volume":"16","author":"A. Barvinok","year":"2016","unstructured":"A. Barvinok: Computing the permanent of (some) complex matrices, Foundations of Computational Mathematics\n16 (2016), 329\u2013342.","journal-title":"Foundations of Computational Mathematics"},{"key":"3357_CR3","doi-asserted-by":"crossref","first-page":"339","DOI":"10.4086\/toc.2015.v011a013","volume":"11","author":"A. Barvinok","year":"2015","unstructured":"A. Barvinok: Computing the partition function for cliques in a graph, Theory of Computing\n11 (2015), 339\u2013355.","journal-title":"Theory of Computing"},{"key":"3357_CR4","volume-title":"Lecture Notes in Computer Science","author":"P. Berman","year":"1999","unstructured":"P. Berman and M. Karpinski: On some tighter inapproximability results (extended abstract), Automata, languages and programming (Prague, 1999) 200-209, in: Lecture Notes in Computer Science, 1644, Springer, Berlin (1999)."},{"key":"3357_CR5","volume-title":"Personal communication","author":"B. Bukh","year":"2015","unstructured":"B. Bukh: Personal communication, (2015)."},{"key":"3357_CR6","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1016\/j.tcs.2005.09.011","volume":"348","author":"A. Bulatov","year":"2005","unstructured":"A. Bulatov and M. Grohe: The complexity of partition functions, Theoretical Computer Science\n348 (2005), 148\u2013186.","journal-title":"Theoretical Computer Science"},{"key":"3357_CR7","doi-asserted-by":"crossref","first-page":"924","DOI":"10.1137\/110840194","volume":"42","author":"J.-Y. Cai","year":"2013","unstructured":"J.-Y. Cai, X. Chen and P. Lu: Graph homomorphisms with complex values: a dichotomy theorem, SIAM Journal on Computing\n42 (2013), 924\u20131029.","journal-title":"SIAM Journal on Computing"},{"key":"3357_CR8","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1006\/jcss.1998.1587","volume":"57","author":"U. Feige","year":"1998","unstructured":"U. Feige and J. Kilian: Zero knowledge and the chromatic number, Journal of Computer and System Sciences\n57 (1998), 187\u2013199.","journal-title":"Journal of Computer and System Sciences"},{"key":"3357_CR9","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"M.X. Goemans and D.P. Williamson: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the Association for Computing Machinery\n42 (1995), 1115\u20131145.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"3357_CR10","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/S0196-6774(02)00217-1","volume":"45","author":"E. Halperin","year":"2002","unstructured":"E. Halperin, R. Nathaniel and U. Zwick: Coloring k-colorable graphs using relatively small palettes, Journal of Algorithms\n45 (2002), 72\u201390.","journal-title":"Journal of Algorithms"},{"key":"3357_CR11","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. H\u00e4stad","year":"1999","unstructured":"J. H\u00e4stad: Clique is hard to approximate within n\n                                    1\u2212\u03b5\n                                    , Acta Mathematica\n                                    182 (1999), 105\u2013142.","journal-title":"Acta Mathematica"},{"key":"3357_CR12","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1145\/274787.274791","volume":"45","author":"D. Karger","year":"1998","unstructured":"D. Karger, R. Motwani and M. Sudan: Approximate graph coloring by semidefinite programming, Journal of the ACM\n45 (1998), 246\u2013265.","journal-title":"Journal of the ACM"},{"key":"3357_CR13","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1103\/PhysRev.87.410","volume":"87","author":"T.D. Lee","year":"1952","unstructured":"T.D. Lee and C.N. Yang: Statistical theory of equations of state and phase transitions. II. Lattice gas and Ising model, Physical Review (2)\n87 (1952), 410\u2013419.","journal-title":"Physical Review (2)"},{"key":"3357_CR14","volume-title":"American Mathematical Society Colloquium Publications, 60, American Mathematical Society, Providence, RI","author":"L. Lov\u00e1sz","year":"2012","unstructured":"L. Lov\u00e1sz: Large Networks and Graph Limits, American Mathematical Society Colloquium Publications, 60, American Mathematical Society, Providence, RI, 2012."},{"key":"3357_CR15","volume-title":"STOC\u201906: Proceedings of the 38th Annual ACM Symposium on Theory of Computing 140-149, ACM, New York","author":"D. Weitz","year":"2006","unstructured":"D. Weitz: Counting independent sets up to the tree threshold, in: STOC\u201906: Proceedings of the 38th Annual ACM Symposium on Theory of Computing 140-149, ACM, New York, 2006."},{"key":"3357_CR16","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1103\/PhysRev.87.404","volume":"87","author":"C.N. Yang","year":"1952","unstructured":"C.N. Yang and T.D. Lee: Statistical theory of equations of state and phase transitions. I. Theory of condensation, Physical Review (2)\n87 (1952), 404\u2013409.","journal-title":"Physical Review (2)"},{"key":"3357_CR17","doi-asserted-by":"crossref","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D. Zuckerman","year":"2007","unstructured":"D. Zuckerman: Linear degree extractors and the inapproximability of max clique and chromatic number, Theory of Computing\n3 (2007), 103\u2013128.","journal-title":"Theory of Computing"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-016-3357-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-016-3357-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-016-3357-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-016-3357-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T21:32:52Z","timestamp":1559079172000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-016-3357-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,10]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,8]]}},"alternative-id":["3357"],"URL":"https:\/\/doi.org\/10.1007\/s00493-016-3357-2","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,5,10]]}}}